Cod sursa(job #2526076)

Utilizator Dan_BDan Bugnariu Dan_B Data 18 ianuarie 2020 11:35:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

string a,b;
int nr=0;
const ll MOD=1000000007,A=69420911;
ll hashA;
vector<ll>powA;
vector<ll>hashB;
vector<int>sol;

void makeHashA()
{
    for(auto c:a)
        hashA=(hashA*A+c)%MOD;
}
void makeHashB()
{
    hashB.push_back(b[0]);
    for(int i=1;i<b.size();i++)
        hashB.push_back((hashB[i-1]*A+b[i])%MOD);
}
void makePowA(int length)
{
    powA.push_back(1);
    for(int i=1;i<=length;i++)
        powA.push_back((powA[i-1]*A)%MOD);
}
ll getHash(int i,int j)
{
    return (!i)?
        hashB[j]:
        (hashB[j]-(hashB[i-1]*powA[j-i+1])%MOD+MOD)%MOD;
}
void solve()
{
    for(int i=0;i<b.size()-a.size();i++)
        if(getHash(i,i+a.size()-1)==hashA)
        {
            sol.push_back(i);
            nr++;
        }
}
int main()
{
    cin>>a>>b;
    makeHashA();
    makeHashB();
    makePowA(b.size());
    solve();
    cout<<nr<<'\n';
    for(auto x:sol)
        cout<<x<<' ';
    return 0;
}