Cod sursa(job #1798945)

Utilizator cicero23catalin viorel cicero23 Data 5 noiembrie 2016 16:42:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000001],s[2000001];
int q1=100007,q2=100021,kmax,z,x,y,xp,yp,v[1002];
int main()
{
    int i;
    f>>p;
    f.get();
    f>>s;
    if(strlen(p)>strlen(s))
        g<<0;
    else{
    int b1=1,b2=1;
    for(i=1;i<strlen(p);i++)
    {
        b1=(b1*128)%q1;
        b2=(b2*128)%q2;
    }
    for(i=0;i<strlen(p);i++)
    {
        x=((x*128)%q1+s[i])%q1;
        y=((y*128)%q2+s[i])%q2;
        xp=((xp*128)%q1+p[i])%q1;
        yp=((yp*128)%q2+p[i])%q2;
    }
    if(x==xp&&y==yp)
    {
        kmax++;
        v[++z]=0;
    }
    for(i=1;i<=strlen(s)-strlen(p)+1;i++)
    {
        x=((x+q1-(s[i-1]*b1)%q1)*128+s[i+strlen(p)-1])%q1;
        y=((y+q2-(s[i-1]*b2)%q2)*128+s[i+strlen(p)-1])%q2;
        if(x==xp&&y==yp){kmax++;if(z<=1000)v[++z]=i;}}
    g<<kmax<<'\n';
    for(i=1;i<=z;i++)
        g<<v[i]<<" ";}
    return 0;
}