Cod sursa(job #2237946)

Utilizator andrei42Oandrei42O andrei42O Data 3 septembrie 2018 23:42:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
#define ll long long
#define P 59
#define MOD1 100049
#define MOD2 100057
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,p;
ll n,m,i,hs,hp,Nr,Hp,Hs,P1=1,P2=1,a[1024];
bool match(ll b, ll k)
{
    if(b==hs && k==hp)
        return true;
    return false;
}
int main()
{
    f>>p>>s;
    n=s.size();
    m=p.size();
    if(m>n)
    {
        g<<"0\n";
        return 0;
    }
    for(i=0; i<m; i++)
    {
        hp=(hp*P+p[i])%MOD1;
        hs=(hs*P+p[i])%MOD2;
        if(i)
        {
            P1=(P1*P)%MOD1;
            P2=(P2*P)%MOD2;
        }
    }
    for(i=0; i<m; i++)
        Hp=(Hp*P + s[i])%MOD1,
        Hs=(Hs*P + s[i])%MOD2;
    if(match(Hs,Hp))
        Nr++,a[Nr]=0;
    for(i=1; i<n-m+1; i++)
    {
       Hp=(((Hp-(s[i-1]*P1)%MOD1)+MOD1)*P+s[i+m-1])%MOD1;
       Hs=(((Hs-(s[i-1]*P2)%MOD2)+MOD2)*P+s[i+m-1])%MOD2;
       if(match(Hs,Hp)){
        Nr++;
        if(Nr<1000)
          a[Nr]=i;
       }
    }
    g<<Nr<<'\n';
    if(Nr>1000)
        Nr=1000;
    for(i=1; i<=Nr; i++)
        g<<a[i]<<' ';

    return 0;
}