Cod sursa(job #2626447)

Utilizator bem.andreiIceman bem.andrei Data 6 iunie 2020 14:52:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("strmatch.in");
ofstream w("strmatch.out");
vector<int>f;
int h[2000002];
const int base=113, mod=1130011;
int main()
{
    string a, b;
    r>>a>>b;
    int n=a.size(), m=b.size();
    long long has=0, inm=base;
    for(int i=n-1; i>=0; i--)
    {
        has+=a[i]*inm;
        has%=mod;
        inm*=base;
        inm%=mod;
    }
    inm=base;
    for(int i=m-1; i>=0; i--)
    {
        h[i]=h[i+1]+b[i]*inm;
        h[i]%=mod;
        inm*=base;
        inm%=mod;
    }
    for(int i=m-n; i>=0; i--)
    {
        long long rez;
        if(h[i]>h[i+n])
        {
            rez=h[i]-h[i+n];
        }
        else
        {
            rez=h[i]+mod-h[i+n];
        }
        if(rez==has)
        {
            f.push_back(i);
        }
        has*=base;
        has%=mod;
    }
    w<<f.size()<<"\n";
    for(int i=f.size()-1; i>=0; i--)
    {
        w<<f[i]<<" ";
    }
    return 0;
}