Cod sursa(job #1260456)

Utilizator papinubPapa Victor papinub Data 11 noiembrie 2014 12:22:50
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
//Rabin-Karp
# include <cstdio>
# include <vector>
# include <cstring>
using namespace std;
FILE *f=freopen("strmatch.in","r",stdin);
FILE *g=freopen("strmatch.out","w",stdout);
vector <int> hash1;
vector <int> hash2;
char s1[2000000] , s2[2000000] , v[1001];
int v1,v2,p1=1,p2=1,h1,h2,nr,n,m;
unsigned int i;
int main()
{
    scanf("%s%s",s1,s2);
    n=strlen(s1);
    m=strlen(s2);
    for (;i<n;i++)
    {
        v1 = (v1*27 + s1[i]) % 10007;
        v2 = (v2*29 + s1[i]) % 666013;
        h1 = (h1*27 + s2[i]) % 10007;
        h2 = (h2*29 + s2[i]) % 666013;
        if(i!=0)
        {
            p1=(p1*27)%10007;
            p2=(p2*29)%666013;
        }
    }
    if (v1==h1 && v2==h2)
    {
        nr++;
        v[nr]=0;
    }
    for (i=n;i<m;i++)
    {
        h1=(((h1 - p1 * s2[i-n]) % 10007 + 10007) * 27 + s2[i]) % 10007;
        h2=(((h2 - p2 * s2[i-n]) % 666013 + 666013) * 29 + s2[i]) % 666013;
        if(v1==h1 && v2==h2)
        {
            nr++;
            if(nr<=1000)
            v[nr]=i-n+1;
        }
    }
    printf("%d\n",nr);
    for (i=1;i<=nr;i++) printf("%d ",v[i]);
    return 0;
}