字符串匹配算法

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”

只要利用之前的结果，就可以减少回溯。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;
}

字符串匹配算法

原文：http://blog.csdn.net/u011608357/article/details/18962301