poj 3461 && hdu 1686 Oulipo （kmp）

题目链接：http://poj.org/problem?id=3461

 

解题报告：字符串匹配关键是next数组不好理解。

 

参考资料写道

（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。

（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符

相同，且j的前面的1—k个字符与开头的1—k

个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。

如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]

（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个

字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。

即T[0]T[1]T[2]。。。T[k-1]==

T[j-k]T[j-k+1]T[j-k+2]…T[j-1]

且T[j] != T[k].（1≤k<j）;

(4) next[j]=0 意义：除（1）（2）（3）的其他情况。

 

 

next数组的值得含义：

1.next[n]=  -1 表示A[m]和B[0]间接比较过了，不相等，下一次比较 A[m+1] 和B[0]

2.next[n]=0 表示比较过程中产生了不相等，下一次比较 A[m] 和B[0]。

3.next[n]= k >0 但k<n, 表示,A[m]的前k个字符与B中的开始k个字符已经间接比较相等了，下一次比   A[m]       和B[k]相等吗？

关于next数组的求法，大家可以参考http://www.cppblog.com/oosky/archive/2006/07/06/9486.html     

 

#include<cstdio>
#include<cstring>
using namespace std;

const int max1 = 10000 + 5;
const int max2 = 1000000 + 5;
int next[max1], len1, len2;

void get_next(char a[])
{
	int i,j=-1;
	memset(next,0,sizeof(next));
	next[0]=-1;
	for(i=1;i<=len1;i++)
	{
		while(j>-1&&a[j+1]!=a[i])
			j=next[j];
		if(a[j+1]==a[i]) 
			j++;
		next[i]=j;
	}
}

int KMP(char a[],char b[])
{
	get_next(a);
	int i,j=-1,cnt=0;
	for(i=0;i<len2;i++)
	{
		while(j!=-1&&a[j+1]!=b[i])
			j=next[j];
		if(a[j+1]==b[i])
			j++;
		if(j==len1-1)
			cnt++;	
	}
	return cnt;
}

int main() 
{
	char w[max1],t[max2];
	int n,ans;
	scanf( "%d",&n );
	while( n-- )
	{
		len1=len2=0;
		scanf("%s %s",w,t);
		for(int i=0;w[i]!='\0';i++) len1++; 
		for(int j=0;t[j]!='\0';j++) len2++;
		int ans = KMP(w,t);
		printf("%d\n",ans);
	}
	return 0;
} 

 

                                                                       

 

 

 

4.