Cod sursa(job #2870788)

Utilizator alexxxxxxhalex alx alexxxxxxh Data 12 martie 2022 16:01:39
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int mod=1e9,baza=31;
char s[2000005],s1[2000005];
int hashs[2000005],hashs1[2000005];
int put[2000005];
int sub1(int i,int j)
{
    return (hashs1[j]-(1LL*hashs1[i-1]*put[j-i+1]%mod)+mod)%mod;
}
vector <int> ans;
int main()
{
    fin >>(s+1)>>(s1+1);
    int n=strlen(s+1);
    int m=strlen(s1+1);
    put[0]=1;

    for (int i=1; i<=n; i++)
    {
        hashs[i]=(1LL*hashs[i-1]*baza+s[i]-'A'+1)%mod;
    }
    for (int i=1; i<=m; i++)
    {
        hashs1[i]=(1LL*hashs1[i-1]*baza+s1[i]-'A'+1)%mod;
        put[i]=1LL*put[i-1]*baza%mod;
    }
    for (int i=1; i<=m-n+1; i++)
    {
        int sb1=sub1(i,i+n-1);
        if (sb1==hashs[n])
        {
            ans.push_back(i);
        }
    }
    fout << ans.size() <<"\n";
    for (int i=0; i<ans.size(); i++) fout << ans[i]-1 <<" ";
}