Cod sursa(job #2237864)

Utilizator andrei42Oandrei42O andrei42O Data 3 septembrie 2018 17:04:18
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define ll long long
#define MOD 101
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,p;
long long n,m,i,hs,hp,h,N,a[1024];
bool verify(ll, ll);
int main()
{
    f>>p>>s;
    n=s.size();
    m=p.size();
    if(m>n)
    {
        g<<"0\n";
        return 0;
    }
    hp=(int)p[0]%MOD,hs=(int)s[0]%MOD;
    for(i=1; i<p.size(); i++)
    {
        hp%=MOD,hs%=MOD;
        hp*=256,hs*=256;
        hp+=p[i],hs+=s[i];
    }
    hp%=MOD,hs%=MOD;
    if(hp==hs)
    {
        if(verify(0,m))
        {
            N++,a[N]=0;
        }
    }
    for(i=1; i<n-m+1; i++)
    {

        hs=(((hs+101)-((int)s[i-1])*((256%101)*256)%101)*256 + (int)s[i+m-1])%101;
        if(hp==hs)
        {
            if(verify(i,i+m))
            {
                N++;
                if(N<=1000)
                    a[N]=i;
            }
        }
    }
    g<<N<<'\n';
    for(i=1; i<=N; i++)
        g<<a[i]<<' ';

    return 0;
}
bool verify(ll start, ll finish)
{
    ll j;
    for(j=0; j<m; j++)
        if(p[j]!=s[start+j])
            return false;
    return true;
}