Cod sursa(job #2674359)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 18 noiembrie 2020 22:47:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>///Rabin-Karp
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
#define p 73
#define MOD1 100007
#define MOD2 100021
char s1[2000009],s2[2000009];
int p1=1,p2=1;
int ans[1009],k,n,m;
int HASH1,HASH2 ,Hash1,Hash2;
int main()
{
        fin>>s1>>s2;
    n=strlen(s1);
    m=strlen(s2);
    for(int i=0;i<n;i++)
    {
        HASH1=(HASH1*p+s1[i])%MOD1;
        HASH2=(HASH2*p+s1[i])%MOD2;
        if(i!=0)
            p1=(p1*p)%MOD1,p2=(p2*p)%MOD2;
    }
    for(int i=0;i<n;i++)
    {
        Hash1=(Hash1*p+s2[i])%MOD1;
        Hash2=(Hash2*p+s2[i])%MOD2;
    }
    if(HASH1==Hash1&&HASH2==Hash2)
        ans[++k]=0;
    for(int i=n;i<m;i++)
    {
        Hash1=((Hash1-(s2[i-n]*p1)%MOD1+MOD1)*p+s2[i])%MOD1;
        Hash2=((Hash2-(s2[i-n]*p2)%MOD2+MOD2)*p+s2[i])%MOD2;
        if(HASH1==Hash1&&HASH2==Hash2)
        {
            k++;
            if(k<=1000)
                ans[k]=i-n+1;
        }
    }
        fout<<k<<'\n';
    for(int i=1;i<=min(1000,k);i++)
        fout<<ans[i]<<' ';
}