Cod sursa(job #3214351)

Utilizator TanasucaGeorgeAlexandruTanasucaGeorgeAlexandru TanasucaGeorgeAlexandru Data 14 martie 2024 08:34:30
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
#define MOD 100007
using namespace std;

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

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

int main()
{
    int i;
    fin >> s >> t;
    n=s.size();
    p=73;
    p1=p2=1;
    for(i=0;i<n;i++){
        ha=(ha*p+s[i])%MOD;
        if(i!=0){
            p1=(p1*p)%MOD;
            ///p2=(p2*p)%MOD;
        }
    }
    for(i=0;i<n;i++){
        hb=(hb*p+t[i])%MOD;
    }
    if(hb==ha) sol.push_back(1);
    for(;i<t.size();i++){
        hb=((hb-(t[i-n]*p1)%MOD+MOD)*p+t[i])%MOD;
        if(ha==hb) 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;
}