Cod sursa(job #2497728)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 23 noiembrie 2019 10:43:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long mod=1000000007;
string a;
string b;
long long val,puteri[2000001],baza,h,ans,sol[2000001],lg;
int main()
{
    fin>>a>>b;
    baza=127;
    puteri[0]=1;
    for(int i=1;i<=a.size()+1;i++)
        puteri[i]=(puteri[i-1]*baza)%mod;
    for(int i=0;i<a.size();i++)
    {
        int x=a.size()-i-1;
        val=(val+puteri[x]*int(a[i]))%mod;
    }
    for(int i=0;i<a.size();i++)
    {
        int x=a.size()-i-1;
        h=(h+puteri[x]*int(b[i]))%mod;
    }
    if(h==val)
    {
       ans++;
       sol[++lg]=0;
    }
    for(int i=1;i<b.size();i++)
    {
        if(i+a.size()-1>=b.size())
            break;
        h=(h-puteri[a.size()-1]*b[i-1])*baza+b[i+a.size()-1];
        if(h==val)
        {
           ans++;
           sol[++lg]=i;
        }
    }
    fout<<ans<<'\n';
    for(int i=1;i<=ans;i++)
        fout<<sol[i]<<" ";
    return 0;
}