Cod sursa(job #1798391)

Utilizator alexandruilieAlex Ilie alexandruilie Data 5 noiembrie 2016 10:44:37
Problema Potrivirea sirurilor Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[10001],p[501];
int z,v[1001],q=701,q1=9001,sq0,sq10,pq,pq1,b1=1,b2=1,nr,nr2,i,num;
int main()
{
    f.get(p,501);
    f.getline(s,100001);
    f.get(s,10001);


    nr=strlen(p);nr2=strlen(s);
    pq=p[0];sq0=s[0];
    for(i=1;i<nr;i++)
    {
        pq=(pq*128+p[i])%q;
        sq0=(sq0*128+s[i])%q;
        b1=(b1*128)%q;
    }
     pq1=p[0];sq10=s[0];
  for(i=1;i<nr;i++)
    {
        pq1=(pq1*128+p[i])%q1;
        sq10=(sq10*128+s[i])%q1;
        b2=(b2*128)%q1;
    }
    for(i=1;i<=nr2-nr+1;i++)
    {if(pq==sq0)
        if(pq1==sq10) {v[++z]=i-1;num++;}
        sq0=(((sq0+701-(s[i-1]*b1)%q)*128)+s[i+nr-1])%q;
         sq10=((sq10+9001-(s[i-1]*b2)%q1)*128%q1+s[i+nr-1])%q1;
        }
        g<<num<<'\n';
        for(i=1;i<=z;i++)
        g<<v[i]<<' ';

    return 0;
}