Cod sursa(job #1165362)

Utilizator teoionescuIonescu Teodor teoionescu Data 2 aprilie 2014 17:29:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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;
int code(char c){
    if('a'<=c && c<='z') return (int(c)-'a'+1);
    if('Z'<=c && c<='Z') return (int(c)-'A'+29);
    if('0'<=c && c<='9') return (int(c)-'0'+59);
}
void RabinKarp(){
    unsigned int id=0,idn=0,pow=1;
    for(int i=0;i<a;i++) id=id*base+code(A[i]),pow=pow*base;
    for(int i=0;i<b;i++){
        idn=idn*base+code(B[i]);
        if(i>=a) idn-=pow*code(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;
}