Cod sursa(job #1649961)

Utilizator 2chainzTauheed Epps 2chainz Data 11 martie 2016 15:57:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000001;
char A[Nmax],B[Nmax];
int N,M,pi[Nmax],ans[1002];
void kmp(){
    int w=0;
    for(int i=1;i<N;i++){
        while(w && A[i]!=A[w]) w=pi[w-1];
        if(A[i]==A[w]) w++;
        pi[i]=w;
    }
    w=0;
    for(int i=0;i<M;i++){
        while(w && B[i]!=A[w]) w=pi[w-1];
        if(B[i]==A[w]) w++;
        if(w==N) ans[min(1001,++ans[0])]=i-N+1;
    }
}
unsigned long long Ba[Nmax],S[Nmax],H;
const unsigned long long base=137;
void rk(){
    Ba[0]=1,S[0]=int(B[0]);
    for(int i=1;i<=M;i++) Ba[i]=Ba[i-1]*base;
    for(int i=0;i<N;i++) H=H*base+int(A[i]);
    for(int i=1;i<M;i++) S[i]=S[i-1]*base+int(B[i]);
    if(S[N-1]==H) ans[min(1001,++ans[0])]=0;
    for(int i=N;i<M;i++) if(S[i]-S[i-N]*Ba[N]==H) ans[min(1001,++ans[0])]=i-N+1;
}
void af(){
    out<<ans[0]<<'\n';
    ans[0]=min(1000,ans[0]);
    for(int i=1;i<=ans[0]-1;i++) out<<ans[i]<<' ';
    if(ans[0]) out<<ans[ans[0]]<<'\n';
}
int main(){
    in.getline(A,Nmax),N=strlen(A);
    in.getline(B,Nmax),M=strlen(B);
    srand(time(0));
    if(rand()%2) kmp();
    else rk(); af();
    return 0;
}