Cod sursa(job #2576803)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 6 martie 2020 23:11:41
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

const int mod=1000000007;

const int prim=666013;

using namespace std;

string str1,str2;

unsigned int nr;

queue <int> ans;

int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    fin>>str1>>str2;
    int_fast64_t ct=1,hash1=0,chash=0;
    for (int i=1;i<str1.length();++i)
    {
        ct*=prim;
        ct%=mod;
    }
    for (int i=0;i<str1.length();++i)
    {
        hash1=hash1*prim+str1[i];
        hash1=hash1%mod;
        chash=chash*prim+str2[i];
        chash%=mod;
    }
    //cout<<hash1<<" "<<chash<<"\n";
    if (chash==hash1)
    {
        ans.push(1);
        nr++;
    }
    for (int i=str1.length();i<str2.length();++i)
    {
        chash=chash-ct*str2[i-str1.length()];
        chash=chash%mod;
        chash=chash*prim+str2[i];
        chash=chash%mod;
        if (chash<0)
        {
            chash+=mod;
        }
        if (chash==hash1)
        {
            ans.push(i-str1.length()+1);
            nr++;
        }
        //cout<<chash<<"\n";
    }
    fout<<nr<<"\n";
    while (!ans.empty())
    {
        fout<<ans.front()<<" ";
        ans.pop();
    }
    return 0;
}