Cod sursa(job #2128626)

Utilizator DanizisSpartanulDani Mocanu DanizisSpartanul Data 11 februarie 2018 21:22:24
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int P=73;
constexpr int MOD1=100007;
constexpr int MOD2=100021;

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

string A,B;
vector<int>sol;

int main()
{
    fin>>A>>B;

    if(A.size()>B.size())
    {
        fout<<"0";
        return 0;
    }

    int P1=1,P2=1;
    int hashA1=0,hashA2=0;
    for(int i=0;i<A.size();i++)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;
        if(i!=0)
            P1=(P1*P)%MOD1, P2=(P2*P)%MOD2;
    }

    int hash1=0,hash2=0;
    for(int i=0;i<A.size();i++)
        hash1=(hash1*P+B[i])%MOD1,
        hash2=(hash2*P+B[i])%MOD2;

    if(hash1==hashA1 && hash2==hashA2)
        sol.push_back(1);

    for(int i=A.size();i<B.size();i++)
    {
        hash1=((hash1-(B[i-A.size()]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        hash2=((hash2-(B[i-A.size()]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
        if(hash1==hashA1 && hash2==hashA2)
            sol.push_back(i-A.size()+1);
    }

    fout<<sol.size()<<"\n";
    for(auto i : sol)
        fout<<i<<" ";

    return 0;
}