HDU1686
题意就是求B串在A串中的出现次数（可重叠
KMP做法
依旧是利用next数组，当某次匹配完成之后，将ans++,然后把j跳转到next[j],，省略不必要的查找。
HDU1686代码
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std ;
const int maxn = 1e6+5;
int Next[maxn];
char str[maxn];
char mo[maxn];
int n1,n2;
void GetNext()
{int i=0,j=-1;while(i<n2){if(j==-1||mo[i]==mo[j]) {++i,++j,Next[i]=j;}else j=Next[j];}return ;
}
int kmp()
{int cnt=0;int i=0,j=0;while(i<n1){if(j==-1||str[i]==mo[j]) i++,j++;else j=Next[j];if(j==n2){cnt++;j=Next[j];//完成一次匹配，将j移动到最长的前缀处，省略不必要的查找}}return cnt;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s%s",mo,str);n1=strlen(str);n2=strlen(mo);Next[0]=-1;GetNext();printf("%d\n",kmp());}return 0;
}Hash做法
我们得到A串的hash值，然后在B中枚举起点，长度为lena的子串，检验hash值是否相同就可以了。
HDU1686代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 1e6+5;
ull xp[maxn],hash_1[maxn],hash_2[maxn];
void init()
{xp[0]=1;for(int i=1;i<maxn;i++)xp[i]=xp[i-1]*13331;
}
ull get_hash(int i,int L,ull hash_[])//get_hash(i,L)可以得到从位置i开始的,长度为L的子串的hash值.
{return hash_[i]-hash_[i+L]*xp[L];
}
int make_hash(char str[],ull hash_[])
{int len=strlen(str);hash_[len]=0;for(int i=len-1;i>=0;i--){hash_[i]=hash_[i+1]*13331+(str[i]-'a'+1);}return len;
}
char str[maxn],str2[maxn];
int main()
{init();int t;scanf("%d",&t);while(t--){int ans=0;scanf("%s%s",str,str2);int len1=make_hash(str,hash_1);int len2=make_hash(str2,hash_2);ull tmp=get_hash(0,len1,hash_1);for(int i=0;i<len2-len1+1;i++)//注意枚举时的边界问题{if(get_hash(i,len1,hash_2)==tmp)ans++;}printf("%d\n",ans);}return 0;
}