Cod sursa(job #906599)

Utilizator FayedStratulat Alexandru Fayed Data 6 martie 2013 22:18:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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=-1;
    Next[0] = 0;
    for(register int x=1;x<m;++x){
        while(k>0 && B[x]!=B[k+1]) k = Next[k];
        if(B[x] == B[k+1])
            k++;
        Next[x] = k;
    }

}

int main(){

  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
 gets(B);
 gets(A);
    int k=-1;
    n = strlen(A);
    m = strlen(B);
    prefix();

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

    }

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

return 0;
}