Cod sursa(job #2641007)

Utilizator etienAndrone Stefan etien Data 9 august 2020 15:52:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long poz[1001];
const long long MOD=1e9+7;
const long long p1=103;
long long cc(char c)
{
    if(c>='a'&&c<='z')
        return c-'a'+1;
    if(c>='A'&&c<='Z')
        return c-'A'+27;
    return c-'0'+53;
}
long long hsh(string s)
{
    long long mod=0,val=1;
    for(long long poz=(long long)s.size()-1;poz>=0;poz--)
    {
        mod=(mod+1LL*val*cc(s[poz]))%MOD;
        val=(1LL*val*p1)%MOD;
    }
    return mod;
}
int main()
{
    string a,b;
    fin>>a>>b;
    long long nr=0,hsa=hsh(a);
    string s=b.substr(0,a.size());
    long long hsb=hsh(s);
    long long put=1;
    for(long long i=1;i<=(long long)a.size();i++)
    {
        put=(1LL*put*p1)%MOD;
        //cout<<put<<" ";
    }
    //cout<<hsa<<"\n";
    for(long long i=a.size();i<(long long)b.size();i++)
    {
        if(hsa==hsb)
        {
            string s=b.substr(i-a.size(),a.size());
            if(s==a)
            {
                nr++;
                if(nr<=1000)
                    poz[nr]=i;
            }
        }
        //cout<<hsb<<" ";
        hsb=(1LL*hsb*p1+cc(b[i]))%MOD;
        hsb-=(1LL*put*(cc(b[i-a.size()])))%MOD;
        if(hsb<0)
            hsb+=MOD;
    }
    if(hsa==hsb)
    {
        string s=b.substr(b.size()-a.size(),a.size());
        if(s==a)
        {
            nr++;
            if(nr<=1000)
                poz[nr]=b.size();
        }
    }
    fout<<nr<<"\n";
    for(int i=1;i<=min(nr,(long long)1000);i++)
        fout<<poz[i]<<" ";
}