POJ3461Oulipo 题解

题目大意：

　　求字符串A在字符串B中出现的次数。

思路：

　　KMP板题，用Hash也可水过~要学习KMP可参考http://blog.csdn.net/u011564456/article/details/20862555

代码：

KMP：

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

char s1[10009],s2[1000009];
int next[10009];

int main()
{
    int n,i,l1,l2,j,ans;
    scanf("%d",&n);
    while (n--)
    {
        scanf("%s%s",s1,s2);
        l1=strlen(s1),l2=strlen(s2);
        for(j=next[0]=0,i=1;i<l1;i++)
        {
            for (;j && s1[j]^s1[i];j=next[j-1]);
            if (s1[i]==s1[j]) j++;
            next[i]=j;
        }
        for (i=j=ans=0;j<l2;j++)
        {
            for (;i && s1[i]^s2[j];i=next[i-1]);
            if (s1[i]==s2[j]) i++;
            if (i==l1) ans++,i=next[i-1];
        }
        printf("%d
",ans);
    }
    return 0;
}

Hash：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int S=999984,mod=1000000007,N=10009,M=1000009;
char s1[N],s2[M];
long long Hash1[N],Hash2[M],mi[M];

int gethash(int l,int r)
{
    return (Hash2[r]-Hash2[l-1]*mi[r-l+1]%mod+mod)%mod;
}

int main()
{
    int n,i,j,l1,l2,ans;
    for (mi[0]=i=1;i<=M;i++) mi[i]=mi[i-1]*S%mod;
    scanf("%d",&n);
    while (n--)
    {
        scanf("%s%s",s1+1,s2+1);
        l1=strlen(s1+1),l2=strlen(s2+1);
        for (i=1;i<=l1;i++) Hash1[i]=(Hash1[i-1]+s1[i])*S%mod;
        for (i=1;i<=l2;i++) Hash2[i]=(Hash2[i-1]+s2[i])*S%mod;
        for (ans=0,i=1;i<=l2-l1+1;i++)
            if (gethash(i,i+l1-1)==Hash1[l1]) ans++;
        printf("%d
",ans);
    }
    return 0;
}