|
子串的定位操作通常稱作串的模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。 設(shè)有2個(gè)串：主串S和子串T，串的簡單模式匹配算法是：從主串S 中的第一個(gè)字符開始和子串T中的第一個(gè)字符比較，分別用i和j 指示S串和T串中正在比較的字符的位置。若相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從主串S的第二個(gè)字符開始再重新與子串的第一個(gè)字符進(jìn)行比較。依次類推，直到子串T中的每個(gè)字符依次和主串S中的一個(gè)連續(xù)字符序列相等，則匹配成功，返回子串T中第一個(gè)字符在主串S中的位置。 主串和子串均采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在單鏈表建立過程中都采用后插法。P指針為主串的頭指針，t指針為子串的頭指針，s和k分別為主串和子串的中間指針，始終指向新建立的結(jié)點(diǎn)。 參考程序： #include<stdio.h> #define null 0 typedef struct node {char ch; struct node *next; }slnode; slnode *p,*t,*s,*k,*first; void *initiate(slnode **h) {*h=(slnode *)malloc(sizeof(slnode)); (*h)->next=null; } slnode append(slnode *p,int x) {slnode *s; s=(slnode *)malloc(sizeof(slnode)); s->ch=x; s->next=null; k->next=s; k=s; } main() {int i,x=0; initiate(&p); k=p; printf("Input main string: "); while(x!=‘\n‘) {x=getchar(); if(x!=‘\n‘) append(p,x); } x=0; initiate(&t); k=t; printf("Input sub-string: "); while(x!=‘\n‘) {x=getchar(); if(x!=‘\n‘) append(t,x); } s=t->next; i=1; s=p->next; first=s; k=t->next; while((s!=null)&&(k!=null)) if(s->ch==k->ch) {s=s->next; k=k->next; } else {i=i+1; //從主串的下一個(gè)字符開始，重新與子串的第一個(gè)字符比較 k=t->next; s=first->next; first=s; } if(k==null) printf("\nmatch postion:%d",i); else printf("\nThe two strings are not matched!"); printf("\n"); }
簡單模式匹配算法因?yàn)橛谢厮菟运俣嚷€有一種改進(jìn)算法，消除了回溯所以加快了匹配速度。這種改進(jìn)算法是D.E.Knuth與V.R.Prett和J.H.Morris同時(shí)發(fā)現(xiàn)的，因此人們稱之為克努特-莫里斯-普拉特操作（簡稱KMP算法）。此算法可以在O(n+m)的時(shí)間數(shù)量級(jí)上完成串的模式匹配操作。改進(jìn)之處在于：當(dāng)每一趟匹配過程中出現(xiàn)字符比較不相等時(shí)，不回溯i指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將子串向右“滑動(dòng)”盡可能遠(yuǎn)的一端距離后，繼續(xù)進(jìn)行比較。 具體實(shí)例，若Si 與Tj不相同，但是主串中從i-j+1到i-1下標(biāo)的字符與子串中從1到j下標(biāo)的字符一一對(duì)應(yīng)。此時(shí)應(yīng)確定子串右移的位數(shù)，然后與主串相應(yīng)位進(jìn)行比較。不妨把與Si進(jìn)行比較的子串字符記作Tk(k<j)。Kunth等人發(fā)現(xiàn)這個(gè)k值僅僅依賴于子串的前j個(gè)字符，而與主串無關(guān)。用next[j]表示與j對(duì)應(yīng)的k值，則表明子串第j個(gè)字符與主串相應(yīng)位失配時(shí)（Si≠Tj），可以用子串中以next[j]為下標(biāo)的字符與主串中Si進(jìn)行比較。若next[j]=0，表明子串中任何字符都不與主串中的Si進(jìn)行比較，主串中下一個(gè)字符Si+1與T1進(jìn)行比較。 Next[j]函數(shù)的定義如下： 0 j=1 next[j]= max{k| 0<k<j 且T1T2…Tk-1=Tj-k+1…Tj-1 1 其他 這樣，改進(jìn)匹配算法與簡單匹配算法不同之處可概括為：當(dāng)匹配過程產(chǎn)生失配時(shí)，指針i不變，指針j退回到next[j]所指示的位置上重新進(jìn)行比較，并且當(dāng)指針j退回至0時(shí)，指針i，j同時(shí)增加1。即若主串的第I個(gè)字符和子串的第i個(gè)字符不匹配時(shí)，應(yīng)該從主串的下一個(gè)字符（Si+1）重新進(jìn)行匹配。 #include<stdio.h> #define null 0 char s[20],t[20]; int next[20]; int i,j,k,s1,t1,index; char x=0; main() {s1=0; t1=0; printf("Input the main string: "); while(x!=‘\n‘) {x=getchar(); if(x!=‘\n‘) {s1++; s[s1]=x; } } printf("\nInput the substring: "); x=0; while(x!=‘\n‘) {x=getchar(); if(x!=‘\n‘) {t1++; t[t1]=x; } } j=1; //求子串的next函數(shù)值，并存入數(shù)組next。 k=0; next[1]=0; while(j<t1) if((k==0)||(t[j]==t[k])) {j=j+1; k=k+1; next[j]=k; } else k=next[k]; printf("\nOut put array next[]:"); for(i=1;i<=t1;i++) printf("%d",next[i]); i=1; j=1; while((i<=s1)&&(j<=t1)) if((j==0)||(s[i]==t[j])) {i=i+1; //繼續(xù)比較后續(xù)字符 j=j+1; } else j=next[j]; //子串向右移動(dòng) if(j>t1) {index=i-t1; printf("\nmatch position:%d\n",index); } else printf("\nThe two strings are not matched!\n"); }
|
|
|
