Cod sursa(job #1969488)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 18 aprilie 2017 14:52:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define Nmax 2000005
#define M1 10007
#define M2 666013
#define P 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[Nmax];
char v[Nmax];
char x[Nmax];
int poz[1001];
int n,m,P1=1,P2=1;
int main()
{f>>v>>s;
int h1=0,h2=0,hash1=0,hash2=0;
for(int i=0;v[i];i++)
{
    h1=(h1*P+v[i])%M1;
    h2=(h2*P+v[i])%M2;
    hash1=(hash1*P+s[i])%M1;
    hash2=(hash2*P+s[i])%M2;
    if(i!=0)
    P1=(P1*P)%M1,
    P2=(P2*P)%M2;
}
n=strlen(v);
m=strlen(s);
if(m<n)
{
    g<<0;
    return 0;
}
int nr=0;
if(h1==hash1 and h2==hash2)
poz[++nr]=0;
for(int i=n;s[i];i++)
{
    hash1=((hash1-(s[i-n]*P1)%M1+M1)*P+s[i])%M1;
    hash2=((hash2-(s[i-n]*P2)%M2+M2)*P+s[i])%M2;
    if(hash1==h1 and h2==hash2)
    {
        nr++;
        if(nr<1001)
            poz[nr]=i-n+1;
    }
}
g<<nr<<'\n';
nr=min(nr,1000);
for(int i=1;i<=nr;i++)
    g<<poz[i]<<' ';

    return 0;
}