Cod sursa(job #2886526)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 7 aprilie 2022 20:56:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, M, hash1, hash2, base=31, pw;
string A, B;
vector<int> sol;

int main()
{
    fin>>A>>B;
    N=A.size();
    M=B.size();

    if(N>M){
        fout<<0;
        return 0;
    }

    for(int i=0;i<N;i++){
        hash1=hash1*base+A[i];
        hash2=hash2*base+B[i];
    }
    pw=1;
    for(int i=1;i<N;i++)
        pw=pw*base;

    if(hash1==hash2)
        sol.push_back(0);

    for(int i=N;i<M;i++){
        hash2=(hash2-B[i-N]*pw)*base+B[i];
        if(hash1==hash2)
            sol.push_back(i-N+1);
    }

    fout<<sol.size()<<'\n';
    int L=min(1000,(int)sol.size());
    for(int i=0;i<L;i++)
        fout<<sol[i]<<' ';

    fin.close();
    fout.close();
}