Cod sursa(job #906609)

Utilizator FayedStratulat Alexandru Fayed Data 6 martie 2013 22:25:38
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMAX 2000001
using namespace std;

int Sol[NMAX];
char A[NMAX],B[NMAX];
int Next[NMAX];
int n,m,nr;

void prefix(){

    int k=0;
    Next[0] = -1;
    for(register int x=1;x<m;++x){
        while(k>0 && B[x]!=B[k]) k = Next[k-1];
        if(B[x] == B[k])
            k++;
        Next[x] = k;
    }

}

int main(){

  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
scanf("%s",&B);
scanf("%s",&A);
    int k=0;
    n = strlen(A);
    m = strlen(B);
    prefix();

    for(register int i=0;i<n;++i){
        while(k>0 && A[i]!=B[k]) k = Next[k-1];
        if(A[i] == B[k]) k++;
            if(k == m){
                Sol[++nr] = i-m+1;
                k = Next[k-1];
            }

    }

printf("%d\n",nr);
for(register int i=1;i<=min(nr,1000);++i)
printf("%d ",Sol[i]);

return 0;
}