Cod sursa(job #2416127)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 26 aprilie 2019 22:22:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

const int mod1=666013,mod2=100003,base=153;

char A[2000010],B[2000010];
int ans[1010];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int hash1=0,hash2=0,p1=1,p2=1,h1=0,h2=0,sol=0,r=0;
    scanf("%s\n",A+1);
    scanf("%s",B+1);
    int l=strlen(A+1),l1=strlen(B+1);
    if(l1<l) {printf("0");return 0;}
    for(int i=1;i<=l;i++)
    {
        hash1=(hash1*base+A[i])%mod1;
        hash2=(hash2*base+A[i])%mod2;
        h1=(h1*base+B[i])%mod1;
        h2=(h2*base+B[i])%mod2;
        if(i<l) {p1=p1*base%mod1,p2=p2*base%mod2;}
    }
    if(hash1==h1 && hash2==h2) {sol++;ans[++r]=0;}
    for(int i=l+1;i<=l1;i++)
    {
        h1=((h1-(p1*B[i-l]%mod1)+mod1)*base+B[i])%mod1;
        h2=((h2-(p2*B[i-l]%mod2)+mod2)*base+B[i])%mod2;
        if(hash1==h1 && hash2==h2)
        {
            sol++;
            if(l<1000) ans[++r]=i-l;
        }
    }
    printf("%d\n",sol);
    for(int i=1;i<=r;i++) printf("%d ",ans[i]);
    return 0;
}