Cod sursa(job #1543263)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 6 decembrie 2015 09:08:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#define maxl 2000005
#include <cstring>

using namespace std;

char M[maxl],N[maxl];
int n,m,prefix[maxl],pos[maxl],res=0;

void Lesen(){
    M[0]=N[0]=' ';
    scanf("%s",N+1);n=strlen(N);
    scanf("%s",M+1);m=strlen(M);
}
void Prafix(){
    int k=0;
    for(int i=2;i<n;i++){
        while(k && N[k+1]!=N[i])k=prefix[k];
        if(N[k+1]==N[i])k++;
        prefix[i]=k;
    }
}
void KMP(){
    int k=0;
    for(int i=1;i<m;i++){
        while(k && N[k+1]!=M[i])k=prefix[k];
        if(M[i]==N[k+1])k++;
        if(k==n-1){
            res++;
            if(res<=1000)pos[res]=i-n+1;
        }
    }
}
void Schreiben(){
    printf("%d\n",res);
    if(res>1000)res=1000;
    for(int i=1;i<=res;++i)printf("%d ",pos[i]);
    printf("\n");
}
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    Lesen();
    Prafix();
    KMP();
    Schreiben();
    return 0;
}