网站建设策划方案如何写/免费申请网站

1.Next数组

next[j]={

j=1时，0

j!=1时，最大子串长度+1，即P1P2….Pk-1==Pj-k+1….Pj-1,1<k<j,(看来j=2时是没有最大子串的,因此next[2]一定为1)

其它情况，1

}

next[j]=0说明模式串与匹配串都要后移一位

next[j]！=0说明匹配串的当前字符与next[j]匹配

next数组的下标从1开始，因此我们在模式串（T）的前面添加一个字符‘#’，初始化next[1]=0

求每个next[j](j>1)时实际上利用到上next[j-1]的值

如求next[5]时，则查看next[4]的值，如果T[4]=T[next[4]]，则next[5]=next[4]+1

如果T[4]!=T[next[4]]，T[4]再与next[T[next[4]]]比，如果相等，则next[5]=next[T[next[4]]]+1,如此继续，如果它的next值为0，则跳到其它情况

因此，标准算法如下：

void get_next()
{unsigned int length = strlen(t);next[0]=0;next[1]=0;unsigned int i=1,j=next[1];while(i<length-1){if(j==0){i++;j=1;next[i]=1;continue;}if(t[i]==t[j]){i++;j++;next[i]=j;}else j = next[j];}}

这段代码优化一下：

scanf("%s",t+1);

t[0]=’#’;

void get_next()
{unsigned int length = strlen(t);//next[0]=0;next[1]=0;unsigned int i=1,j=next[1];while(i<length-1){if(j==0||t[i]==t[j]){i++;j++;next[i]=j;}else j = next[j];}}

对于POJ3461,next数组要多求一位

要求：求出上串在下串中出现的次数

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

#include <iostream>
using namespace std;
#define MAX 1000003
unsigned int next[MAX];
char s[MAX];
char t[MAX];
void get_next()
{unsigned int length = strlen(t);next[0]=0;next[1]=0;unsigned int i=1,j=next[1];while(i<length){if(j==0||t[i]==t[j]){i++;j++;next[i]=j;}else j = next[j];}}
unsigned int kmp(){unsigned int length = strlen(s)-1;unsigned int matLen = strlen(t)-1;if(length<matLen)return 0;unsigned int i=1,j=1,count = 0;while(i<=length){if(j==0||s[i]==t[j]){i++;j++;}else j = next[j];if(j==matLen+1){count++;j = next[j]; }}return count;
}int main()
{freopen("i://in.txt","r",stdin);int count;scanf("%d",&count);t[0]='#';s[0]='#';for(int i=0;i<count;i++){scanf("%s",t+1);scanf("%s",s+1);get_next();printf("%d\n",kmp());}return 0;
}