Cod sursa(job #1165390)

Utilizator teoionescuIonescu Teodor teoionescu Data 2 aprilie 2014 17:38:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000001;
char A[Nmax],B[Nmax];
int a,b,pi[Nmax];
int many,Ans[1001];
void KMP(){
    int w=0;
    for(int i=1;i<a;i++){
        while(w!=0 && A[w]!=A[i]) w=pi[w-1];
        if(A[w]==A[i]) w++;
        pi[i]=w;
    }
    w=0;
    for(int i=0;i<b;i++){
        while(w!=0 && A[w]!=B[i]) w=pi[w-1];
        if(A[w]==B[i]) w++;
        if(w==a) if(++many<=1000) Ans[many]=i-a+1;
    }
}
const int base = 73;
void RabinKarp(){
    unsigned id=0,idn=0,pow=1;
    for(int i=0;i<a;i++) id=id*base+A[i],pow=pow*base;
    for(int i=0;i<b;i++){
        idn=idn*base+B[i];
        if(i>=a) idn-=pow*B[i-a];
        if(id==idn) if(++many<=1000) Ans[many]=i-a+1;
    }
}
int main(){
    in.getline(A,Nmax);a=strlen(A);
    in.getline(B,Nmax);b=strlen(B);
    srand(time(NULL));
    if(rand()%2==0) KMP();
    else RabinKarp();
    out<<many<<'\n';
    for(int i=1;i<=min(many,1000);i++) out<<Ans[i]<<' ';out<<'\n';
    return 0;
}