Cod sursa(job #1501577)

Utilizator 2chainzTauheed Epps 2chainz Data 13 octombrie 2015 17:29:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
#include<cstring>
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],sol,K,ans[1002];
int main(){
    in.getline(A,Nmax),N=strlen(A);
    in.getline(B,Nmax),M=strlen(B);
    int w=0;
    for(int i=1;i<N;i++){
        while(w && A[w]!=A[i]) w=pi[w-1];
        if(A[w]==A[i]) w++;
        pi[i]=w;
    }
    w=0;
    for(int i=0;i<M;i++){
        while(w && A[w]!=B[i]) w=pi[w-1];
        if(A[w]==B[i]) w++;
        if(w==N){
            sol++,ans[++K]=i-N+1;
            if(K>1000) K--;
        }
    }
    out<<sol<<'\n';
    for(int i=1;i<K;i++) out<<ans[i]<<' ';
    if(K) out<<ans[K]<<'\n';
    return 0;
}