Cod sursa(job #1553772)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 20 decembrie 2015 14:55:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
///KMP
#include <cstdio>
#define maxl 2000005
#include <cstring>

using namespace std;

char M[maxl],N[maxl];
int n,m;
int prefix[maxl],poz[maxl],rez;

void citeste();
void Prefix();
void KMP();

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    citeste();
    Prefix();
    KMP();
    return 0;
}
void citeste(){
    N[0] = ' '; M[0] = ' ';
    gets(N+1); n = strlen(N);
    gets(M+1); m = strlen(M);
}
void Prefix(){
    int q = 0,i;
    for(i = 2;i < n;++i){
        while(q && N[q+1] != N[i])q = prefix[q];
        if(N[q+1] == N[i])q++;
        prefix[i] = q;
    }
}
void KMP(){
    int i,k = 0;
    for(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){
            rez++;
            if(rez<1000)poz[rez] = i - n + 1;
        }
    }
    printf("%d\n",rez);
    if(rez>1000)rez = 1000;
    for(i=1;i<=rez;++i)printf("%d ",poz[i]);
}