Cod sursa(job #2870782)

Utilizator alexxxxxxhalex alx alexxxxxxh Data 12 martie 2022 15:58:36
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 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<=m;i++) put[i]=1LL*put[i-1]*baza%mod;
    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;
    }
    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 <<" ";
}