KMP算法就是求母串中字串的长度或者字串出现的次数，相对于暴力求解的话，KMP算法节省时间，KMP算法就是分两部分next[ ]和kmp中找字串。next[ ]算法是找字串中的前后缀的长度，这样在KMP中寻找时就节省了时间。
next[ ]函数代码：
void get_next(char s2[],int m) { int i=1,j=0; nex[0]=-1;//初始next[0]=-1 while(i<m) { if(j==-1||s2[i]==s2[j]) { i++; j++; nex[i]=j; } else j=nex[j]; } }
KMP代码：
int kmp(char str1[],char str2[]) { int i=0,j=0,m; n=strlen(str1); m=strlen(str2); get_next(str2,m); while(i<n&&j<m) { if(j==-1||str1[i]==str2[j])//逐个取寻找 { i++; j++; } else j=nex[j]; } }
例题解释：
题目：
一般来说，字符串处理存在很多问题。现在你遇到另一个这样的
问题。如果你得到两个字符串，例如“asdf”和“sdfg”，它们之间的加法结果是“asdfg”，
“sdf”是“asdf”的尾子串和“sdfg”的头子串。然而，结果是“asdfghjk”，
当你必须添加“asdf”和“ghjk”并保证最短的字符串，然后最小的词典
第二，其他增加的规则相同。
输入
对于每种情况，有两个字符串（选择的字符只是’a’到’z’），每个字符串的长度不超过10 ^ 5且不为空。
输出
打印本书的最终字符串。打印本书的最终字符串。
Sample Input
asdf sdfg asdf ghjk
Sample Output
asdfg asdfghjk
解题思路： 给两个字符串分别作为母串和子串，输出两个和的最短字符串，如abcde+bcdekl结果为abcdekl，就是找第一个字符串的后缀与第二个字符串的前缀相同的最大长度。 注意：如果两个字符串不管谁做母串所得的前缀和后缀的最大长度都一样，则就用strcmp()判断最小字典输出。
程序代码：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; int nex[500000],n; char s[500000],s1[500000]; void get_next(char s2[],int m) { int i=1,j=0; nex[0]=-1; while(i<m) { if(j==-1||s2[i]==s2[j]) { i++; j++; nex[i]=j; } else j=nex[j]; } } int kmp(char str1[],char str2[]) { int i=0,j=0,m; n=strlen(str1); m=strlen(str2); get_next(str2,m); while(i<n&&j<m) { if(j==-1||str1[i]==str2[j]) { i++; j++; } else j=nex[j]; } if(i==n) return j; else return 0; } int main() { int i,k1,k2,j; while(cin>>s>>s1) { k1=kmp(s,s1); k2=kmp(s1,s);//找出两个最长的前缀和后缀相同的长度 if(k1>k2) { cout<<s<<s1+k1<<endl; } else if(k1<k2) { cout<<s1<<s+k2<<endl; } else { if(strcmp(s,s1)<0)//按字典顺序输出 cout<<s<<s1+k1<<endl; else cout<<s1<<s+k2<<endl; } } return 0; }
