Cod sursa(job #2046427)

Utilizator enedumitruene dumitru enedumitru Data 23 octombrie 2017 19:59:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <cstring>
#define Dmax 2000005
#define d 73
#define q 100007
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char P[Dmax],T[Dmax],v[Dmax];
int Nr;
int main()
{   f>>(P+1)>>(T+1);
    int m=strlen(P+1),n=strlen(T+1);
    if(m>n) {g<<"0\n"; g.close(); return 0;}
    int h=1;
    for(int i=1;i<m;i++) h=h*d%q;
    int p=0,t=0;
    for(int i=1;i<=m;i++)
    {   p=(p*d+P[i])%q;
        t=(t*d+T[i])%q;
    }
    for(int s=0;s<=n-m;s++)
    {   if(p==t)
        {   //if(verif(s))
                {Nr++; v[s]=1;}
        }
        if(s<n-m) t=((d*(t-T[s+1]*h)+T[s+m+1])%q+q)%q;
    }
    g<<Nr<<'\n';
    Nr=0;
    for(int i=0;i<n && Nr<1000;i++)
        if(v[i]) {Nr++; g<<i<<' ';}
    g<<'\n'; g.close(); return 0;
}