Cod sursa(job #744675)

Utilizator test0Victor test0 Data 9 mai 2012 13:26:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 2000002
using namespace std;
int n,m,u[MAX],r[1001],nr;
char A[MAX],B[MAX];

void prefix(){
    int i,k=-1;
    u[0]=k;
    for(i=1;i<n;i++){
        while(k>-1&&A[k+1]!=A[i])k=u[k];
        if(A[k+1]==A[i])k++;
        u[i]=k;
    }
}

void kmp(){
    int i,k=-1;
    for(i=0;i<m;i++){
        while(k>-1&&A[k+1]!=B[i])k=u[k];
        if(A[k+1]==B[i])k++;
    if(k==n-1){
        nr++;
        if(nr<=1000)r[nr]=i-n+1;
        k=u[k]; }
    }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
        scanf("%s ",&A); n=strlen(A);
        scanf("%s ",&B); m=strlen(B);
    prefix();
    kmp();
   printf("%d\n",nr);
   for(int i=1;i<=min(nr,1000);i++)printf("%d ",r[i]);
   return 0;
}