Cod sursa(job #2430135)

Utilizator georgeoctavianGeorge Octavian Grumazescu georgeoctavian Data 12 iunie 2019 21:05:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;
#define baza 31
#define mod 1000000007
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long ba=1,nr,verif,ans[2000010];
int k;
string a,b;
int main()
{
    fin>>a>>b;
    int n=a.size(),m=b.size();
    for(int i=n-1;i>=0;i--)
    {
        verif=(verif+a[i]*ba)%mod;
        nr=(nr+b[i]*ba)%mod;
        ba=(ba*baza)%mod;
    }
    if(nr==verif)
        k=1;
    for(int i=n;i<m;i++)
    {
        nr=(((nr*baza)%mod-(b[i-n]*ba)%mod)%mod+b[i])%mod;
        nr=(nr+mod)%mod;
        if(nr==verif)
            ans[++k]=i-n+1;
    }
    fout<<k<<'\n';
    int p=min(1000,k);
    for(int i=1;i<=p;i++)fout<<ans[i]<<' ';
    return 0;
}