KMP算法C语言代码实现.doc

/*在Visual Studio 2008环境下调试*/#include #include #include /*改进型与非改进型区别就在于算出nexti的值后再向前取出nexti-1为下标的tnexti-1的字符*并将其与当前不匹配的字符是否相同相同则nexti=nextnexti-1*还有就是若是当前不匹配的值与字串的每一个字符相同则nexti=0*/*（）next1=0 意义：任何串的第一个字符的模式值规定为。（）nextj=k 意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，即: T1T2Tk-1 = Tj-k+1Tj-k+2Tj-1（）nextj=1 其他情况。*/* 设在字符串S中查找模式串T，若Sm!=Tn,那么，取Tn的模式函数值nextn,（）、 nextn= 0 表示Sm和T1间接比较过了，不相等，下一次比较Sm+1 和T1（）、 nextn=1 表示比较过程中产生了不相等，下一次比较Sm 和T1。（）、 nextn= k 表示Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？（）、其他值，不可能。*/void GetStrNext(char t,int next)/获取next数组的值非改进型int len=0;int i=0,j=0,k=0,l=0,m=0,n=0;char ch=0;len=strlen(t);while(ilen)if(i=0)nexti=0;else if (i=1)nexti=1;elsel=i-1;j=1;/从子串第个字符开始与子串第一个字符开始比较一直到当前不匹配的前一个字符处k=0;while(j=l)ch=tj;if(ch=tk)m=j;n=k;while(ml)nexti=i-j+1;elsenexti=1;else if(m=l)nexti=1;j+;i+;j=strlen(t);/*for(i=0;ij;i+)printf(%d ,nexti);printf(n);_getch();*/void GetStrNextval(char t,int next)/获取next数组的值改进型int len=0;int i=0,j=0,k=0,l=0,m=0,n=0;char ch=0;len=strlen(t);while(ilen)if(i=0)nexti=0;else if (i=1)nexti=1;elsel=i-1;j=1;/从子串第个字符开始与子串第一个字符开始比较一直到当前不匹配的前一个字符处k=0;while(j=l)ch=tj;if(ch=tk)m=j;n=k;while(ml)nexti=i-j;if(ch=tnexti)if(ch!=t0)nexti=nextnexti;elsenexti=0;elseNULL;else if(ch!=t0)nexti=1;elsenexti=0;else if(m=l & ti!=t0)nexti=1;elsenexti=0;j+;i+;j=strlen(t);/*for(i=0;ij;i+)printf(%d ,nexti);printf(n);_getch();*/void FindTStr(char s,char t,int next)/根据next数组的值进行查找int lens=0,lent=0,i=0,j=0,pos=0,flag=0;lens=strlen(s);lent=strlen(t);pos=i;while(ilens)while(jlens-pos-1 & !flag)printf(Not Find!n);int main()char sN;char tN;int nextN;/GetStrNext(t,next);printf(Please input main string:n);gets_s(s);printf(Please inp