|
子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一。 设有2个串：主串S和子串T，串的简单模式匹配算法是：从主串S 中的第一个字符开始和子串T中的第一个字符比较，分别用i和j 指示S串和T串中正在比较的字符的位置。若相等，则继续逐个比较后续字符；否则从主串S的第二个字符开始再重新与子串的第一个字符进行比较。依次类推，直到子串T中的每个字符依次和主串S中的一个连续字符序列相等，则匹配成功，返回子串T中第一个字符在主串S中的位置。 主串和子串均采用链式存储结构，在单链表建立过程中都采用后插法。P指针为主串的头指针，t指针为子串的头指针，s和k分别为主串和子串的中间指针，始终指向新建立的结点。 参考程序： #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; //从主串的下一个字符开始，重新与子串的第一个字符比较 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"); }
简单模式匹配算法因为有回溯所以速度慢，还有一种改进算法，消除了回溯所以加快了匹配速度。这种改进算法是D.E.Knuth与V.R.Prett和J.H.Morris同时发现的，因此人们称之为克努特-莫里斯-普拉特操作（简称KMP算法）。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。改进之处在于：当每一趟匹配过程中出现字符比较不相等时，不回溯i指针，而是利用已经得到的“部分匹配”的结果将子串向右“滑动”尽可能远的一端距离后，继续进行比较。 具体实例，若Si 与Tj不相同，但是主串中从i-j+1到i-1下标的字符与子串中从1到j下标的字符一一对应。此时应确定子串右移的位数，然后与主串相应位进行比较。不妨把与Si进行比较的子串字符记作Tk(k<j)。Kunth等人发现这个k值仅仅依赖于子串的前j个字符，而与主串无关。用next[j]表示与j对应的k值，则表明子串第j个字符与主串相应位失配时（Si≠Tj），可以用子串中以next[j]为下标的字符与主串中Si进行比较。若next[j]=0，表明子串中任何字符都不与主串中的Si进行比较，主串中下一个字符Si+1与T1进行比较。 Next[j]函数的定义如下： 0 j=1 next[j]= max{k| 0<k<j 且T1T2…Tk-1=Tj-k+1…Tj-1 1 其他 这样，改进匹配算法与简单匹配算法不同之处可概括为：当匹配过程产生失配时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退回至0时，指针i，j同时增加1。即若主串的第I个字符和子串的第i个字符不匹配时，应该从主串的下一个字符（Si+1）重新进行匹配。 #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函数值，并存入数组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; //继续比较后续字符 j=j+1; } else j=next[j]; //子串向右移动 if(j>t1) {index=i-t1; printf("\nmatch position:%d\n",index); } else printf("\nThe two strings are not matched!\n"); }
|
|
|
