Cod sursa(job #2468486)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 5 octombrie 2019 16:12:51
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define B 128
#define m1 100007
#define m2 100003
#define Nmax 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char a[Nmax], b[Nmax];
vector <int> s;
int n, m, i;
long long ha1, ha2, hb1, hb2, p1, p2;
int main()
{
    fin.getline(a, 1000);
    fin.getline(b, 1000);
    n=strlen(a);
    m=strlen(b);
    p1=p2=1;
    for(i=0; i<n; i++)
    {
        ha1=(ha1*B+a[i])%m1;
        ha2=(ha2*B+a[i])%m2;
        hb1=(hb1*B+b[i])%m1;
        hb2=(hb2*B+b[i])%m2;
        if(i)
        {
            p1=(p1*B)%m1;
            p2=(p2*B)%m2;
        }
    }
    if(ha1==hb1&&ha2==hb2)
        s.push_back(0);
    for(i=1; i<=m-n; i++)
    {
        hb1=(((hb1-(p1*b[i-1])%m1+m1)%m1)*B+b[i+n-1])%m1;
        hb2=(((hb2-(p2*b[i-1])%m2+m2)%m2)*B+b[i+n-1])%m2;
        if(ha1==hb1&&ha2==hb2)
        {
            s.push_back(i);
            if(s.size()==1000)
                break;
        }
    }
    fout << s.size() << '\n';
    for(i=0; i<s.size(); i++)
        fout << s[i] << ' ';
    return 0;
}