Cod sursa(job #1098906)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 5 februarie 2014 12:24:15
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <cstring>

using namespace std;
int n, m, i, t, p1, p2, x, ap1, ap2, bp1, bp2, v[2000009];
int pprim1[699700], pprim2[699700];
char a[2000009], b[2000009];
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(a);
    gets(b);
    n=strlen(a);
    m=strlen(b);
    if(n>m) {printf("0");return 0;}
    p2=686969;
    p1=666013;
    pprim1[0]=1;
    pprim2[0]=1;
    for(i=1;i<=100009;i++)
    {
        pprim1[i]=(pprim1[i-1]*73)%p1;
        pprim2[i]=(pprim2[i-1]*73)%p2;
    }
    x=0;
    for(i=n-1;i>=0;i--)
    {
        ap1=(ap1+(a[i])*pprim1[x])%p1;
        ap2=(ap2+(a[i])*pprim2[x])%p2;
        bp1=(bp1+(b[i])*pprim1[x])%p1;
        bp2=(bp2+(b[i])*pprim2[x])%p2;
        x++;
    }
    x--;
    t=0;
    if(ap1==bp1&&ap2==bp2)
    {
        t++;
        v[t]=0;
    }
    for(i=1;i<=m-n-1;i++)
    {
        bp1=((bp1-(b[i-1]*pprim1[x])%p1+p1)*73+b[i+n-1])%p1;
        bp2=((bp2-(b[i-1]*pprim2[x])%p2+p2)*73+b[i+n-1])%p2;
        if(ap1==bp1&&ap2==bp2)
        {
            t++;
            v[t]=i;
        }
    }
    printf("%d\n", t);
    for(i=1;i<=t;i++)
        printf("%d ", v[i]);
    return 0;
}