Cod sursa(job #1789419)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 26 octombrie 2016 23:30:26
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <cstring>

char sir1[2000010],sir2[2000010];
const int mod1=666013,mod2=100007,baza=153;
int v[2000010];

using namespace std;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int l1,l2,p1,p2,hash1=0,hash2=0,hash11=0,hash22=0,sol=0;
    scanf("%s\n%s",sir1,sir2);
    l1=strlen(sir1);
    l2=strlen(sir2);
    p1=1;
    p2=1;
    for(int i=0;i<l1;i++)
    {
        hash1=(hash1*baza+sir1[i])%mod1;
        hash2=(hash2*baza+sir1[i])%mod2;
        if(i<l1-1)
        {
            p1=(p1*baza)%mod1;
            p2=(p2*baza)%mod2;
        }
    }
    if(l1>l2)
    {
        printf("0");
        return 0;
    }
    for(int i=0;i<l1;i++)
    {
        hash11=(hash11*baza+sir2[i])%mod1;
        hash22=(hash22*baza+sir2[i])%mod2;
    }
    if(hash1==hash11 && hash2==hash22)
    {
        sol++;
        v[sol]=0;
    }
    for(int i=l1;i<l2;i++)
    {
        hash11=((hash11-(sir2[i-l1]*p1)%mod1)*baza+sir2[i])%mod1;
        hash22=((hash22-(sir2[i-l1]*p2)%mod2)*baza+sir2[i])%mod2;
        if(hash11==hash1 && hash22==hash2)
        {
            sol++;
            v[sol]=i-l1+1;
        }
    }
    printf("%d\n",sol);
    for(int i=1;i<=sol;i++)
        printf("%d ",v[i]);
    return 0;
}