1.普通的字符串匹配算法可以从开始处逐个匹配字符，遇到不相等的情况，可以回溯，从上次的下一个位置开始，继续逐个匹配，下面是程序：
# include <iostream>
using namespace std;
# include <string>
int main()
{
int find(string,string );
string s1("hello world ");
string s2(" world");
cout<<find(s1,s2)<<endl;
cin.get();
return 0;
}
int find(string s1,string s2)
{
int i=0,j=0;
while(i<s1.length()&&j<s2.length())
{
int t=i;
if(s1[i]==s2[j])
{
i++;j++;
}
else
{
j=0;i=t+1;
}
}
if(j==s2.length())
return 1;
else
return 0;
}
匹配的过程是：
假设长字符串的长度为n，匹配字符串的长度为m，上面算法的平均复杂度是O(m*n)，如果有一下的字符串，s1=”aaaa…b”,前面有100个a,s2=”aaaaab”,用上面的方法进行匹配时，将会回溯95次，这是非常低效的，提高字符串的匹配效率可以用KMP算法。
2 KMP算法
KMP算法的思想是利用已经比较出的结果，减少回溯发生的次数，从而降低算法的复杂度，
KMP算法实现字符串匹配的例子如下：
假设长串s1=”abadab”,s2=”abacad”
匹配的过程是:s1[3]和s2[3]遇到不相等的字符，这时next[3]=1,接下来会比较s1[3]与s2[1]，因为next[3]为1表示s2[3]和s[3]前面的一个字符已经比较过而且相等，下次再进行比较时，
只要利用之前的结果，就可以减少回溯。next[j]的值确定方法是：
（1）next[0]=-1,第一个字符的值为-1
（2）next[j]=-1 串s2中下标为j的字符，如果与首字符相同，且j前面的k-1个字符与开头的k-1个字符不等（或者相等但s2[k]==s2[j]）(1<=k<j)
（3）next[j]=k s2中下标为j的字符，如果j前面的k个字符与开头的k个字符相等，且s2[j]!=s2[k] (1<=k<j)
（4）next[j]=0 其它
例如长串s1=”baabadda”,s2=”ababc”
next[j]分别为-1 0 -1 1 2
next函数表示方法如下:
void next(const char *s,int next[])
{
int j=0,k=-1;
next[0]=-1;
while(s[j]!='\0')
{
if(k==-1||s[j]==s[k])
{
+j;++k;
if(s[j]!=s[k])
next[j]=k;
else
next[j]=next[k];
}
else
k=next[k];
}
for(int i=0;i<j;i++)
{
cout<<next[i]<<endl;
}
cout<<endl;
}