Cod sursa(job #1278481)

Utilizator ZoranZomboratZoran Zomborat Goran ZoranZomborat Data 28 noiembrie 2014 22:32:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
using namespace std;

#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>
#define N_max 2000005
#define mod 50331653

char a[N_max],b[N_max];
int n,m;
vector<int> apar;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main()
{
int i=0,nr;
int hash_a=0,hash_b=0,pow=1;
fin>>a>>b;
n=strlen(a);
while(i<n)
{
hash_a=(hash_a*52+a[i])%mod;
hash_b=(hash_b*52+b[i])%mod;
pow*=52;
pow%=mod;
i++;
}
m=strlen(b);
for(i=n;i<m;i++)
{   cout<<hash_a<<"/"<<hash_b<<endl;
    if(hash_a==hash_b)
        apar.push_back(i-n);
    hash_b=(52*hash_b%mod+b[i]-(pow*b[i-n])%mod+mod)%mod;
}
n=min((int)apar.size(),1000);
fout<<apar.size()<<endl;
for(int i=0;i<n;i++)
    fout<<apar[i]<<" ";
}