Cod sursa(job #1255795)

Utilizator andreismara97Smarandoiu Andrei andreismara97 Data 5 noiembrie 2014 10:04:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");


char x[2000001],y[2000001];

int main ()
{
    int v1=0,v2=0,h1=0,h2=0;
    int nr=0,v[1001];
    in.getline(x,2000001);
    in.getline(y,2000001);
    int n=strlen(x),m=strlen(y);
    int p1=1,p2=1;
    for(int i=0;i<n;i++)
    {
        v1=(27*v1+x[i])%10007;
        v2=(29*v2+x[i])%666013;
        h1=(27*h1+y[i])%10007;
        h2=(29*h2+y[i])%666013;
        if(i!=0)
        {
            p1=(p1*27)%10007;
            p2=(p2*29)%666013;
        }
    }
    if(v1==h1 && v2==h2)
    {
        nr++;
        v[nr]=0;
    }
    for(int i=n;i<m;i++)
    {
        h1=(((h1-p1*y[i-n])%10007+10007)*27+y[i])%10007;
        h2=(((h2-p2*y[i-n])%666013+666013)*29+y[i])%666013;
        if(v1==h1 && v2==h2)
        {
            nr++;
            v[nr]=i-n+1;
        }
        if(nr==1000)
            break;
    }
    out<<nr<<'\n';
    for(int i=1;i<=nr;i++)
        out<<v[i]<<' ';
    return 0;
}