Cod sursa(job #896220)

Utilizator sanzianaioneteIonete Sanziana sanzianaionete Data 27 februarie 2013 14:26:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int a1,a2,b1,b2,bz=91,bz2=97,m1=666019,m2=666013,p1=1,p2=1,l1,l2,nr=0;
char a[2000002],b[2000002];
int poz[2000002];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a);
    gets(b);
    l1=strlen(a);
    l2=strlen(b);
    if(l1>l2){printf("0\n");return 0;}
    for(int i=1;i<l1;++i)
    {
        p1=(p1*bz)%m1;
        p2=(p2*bz2)%m2;
    }
    for(int i=0;i<l1;++i)
    {
        a1=(a1*bz+a[i])%m1;
        a2=(a2*bz2+a[i])%m2;
        b1=(b1*bz+b[i])%m1;
        b2=(b2*bz2+b[i])%m2;
    }
    if(a1==b1&&a2==b2) {poz[0]=0;++nr;}
    for(int i=l1;i<l2;++i)
    {
        b1=((b1+m1-(p1*b[i-l1])%m1)*bz+b[i])%m1;
        b2=((b2+m2-(p2*b[i-l1])%m2)*bz2+b[i])%m2;
        if(a1==b1&&a2==b2)
        {
            poz[nr]=i-l1+1;
            ++nr;
        }
    }
    printf("%d\n",nr);
    if(nr>1000) nr=1000;
    for(int i=0;i<nr;++i)
        printf("%d ",poz[i]);
    printf("\n");
    return 0;

}