Cod sursa(job #2238040)

Utilizator andrei42Oandrei42O andrei42O Data 4 septembrie 2018 12:09:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define LMAX 2000043
#define P 59
#define MOD1 100049
#define MOD2 100057
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[LMAX],p[LMAX];
int n,m,hs,hp,P1=1,P2=1,a[2000005];
int main()
{
    f>>p>>s;
    f.close();
    n=strlen(s);
    m=strlen(p);
    hs=hp=0;
    for(int 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;
    }
    if(m>n)
    {
        g<<"0\n";
        return 0;
    }
    int Hp=0, Hs=0;
    for(int i=0; i<m; i++)
        Hp=(Hp*P + s[i])%MOD1,
        Hs=(Hs*P + s[i])%MOD2;
    int Nr=0;
    if(hs==Hs && Hp==hp)
        Nr++,a[0]=1;
    for(int 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(hs==Hs && Hp==hp){
        a[i]=1,Nr++;
       }
    }
    g<<Nr<<'\n';
    Nr=0;
    for(int i=0; i<n && Nr<1000; i++)
        if(a[i])
        Nr++,
        g<<i<<" ";
    g<<'\n';
    g.close();

    return 0;
}