Cod sursa(job #3214355)

Utilizator TanasucaGeorgeAlexandruTanasucaGeorgeAlexandru TanasucaGeorgeAlexandru Data 14 martie 2024 08:37:50
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define MOD1 100007
#define MOD2 100021
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector<int> sol;
string s,t;
int n,p,p1,p2,ha1,hb1,ha2,hb2;

int main()
{
    int i;
    fin >> s >> t;
    n=s.size();
    p=73;
    p1=p2=1;
    for(i=0;i<n;i++){
        ha1=(ha1*p+s[i])%MOD1;
        ha2=(ha2*p+s[i])%MOD2;
        if(i!=0){
            p1=(p1*p)%MOD1;
            p2=(p2*p)%MOD2;
        }
    }
    for(i=0;i<n;i++){
        hb1=(hb1*p+t[i])%MOD1;
        hb2=(hb2*p+t[i])%MOD2;
    }
    if(hb1==ha1 && hb2==ha2) sol.push_back(1);
    for(;i<t.size();i++){
        hb1=((hb1-(t[i-n]*p1)%MOD1+MOD1)*p+t[i])%MOD1;
        hb2=((hb2-(t[i-n]*p2)%MOD2+MOD2)*p+t[i])%MOD2;
        if(hb1==ha1 && hb2==ha2) sol.push_back(i-n+1);
    }
    fout << sol.size() << "\n";
    n=sol.size();
    for(i=0;i<min(1000,n);i++) fout << sol[i] << " ";
    return 0;
}