Cod sursa(job #1009266)

Utilizator teoionescuIonescu Teodor teoionescu Data 12 octombrie 2013 19:49:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<cstring>
#define min(x,y) (x<y?x:y)
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000005;
const unsigned int a = 73;
unsigned int hashA,hashB,pow=1;
char A[Nmax],B[Nmax];
int N,M;
int sol[1005],rasp;
void checkEq(int i){
    if(hashA==hashB)
        if(rasp<1000) sol[++rasp]=i-M+1;
        else ++rasp;
}
int main(){
    int i;
    in.getline(B,Nmax);
    in.getline(A,Nmax);
    N=strlen(A);
    M=strlen(B);
    for(i=0;i<M;i++){
        hashA=hashA*a+A[i];
        hashB=hashB*a+B[i];
        pow*=a;
    }
    checkEq(i-1);
    for(;i<N;i++){
        hashA = hashA*a - pow*A[i-M] + A[i];
        checkEq(i);
    }
    out<<rasp<<'\n';
    for(i=1;i<=min(rasp,1000);i++) out<<sol[i]<<' ';
    return 0;
}