Cod sursa(job #759119)

Utilizator test13test13 test13 Data 16 iunie 2012 18:58:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1<<21

int n,nr,pos[1001],u[MAX];
char a[MAX],b[MAX];

void prefix(){
    int k=-1;
    u[0]=k;
    for(int i=1;a[i]!='\n' && a[i]!='\0';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 k=-1;
    for(int i=0;b[i]!='\n' && b[i]!='\0';i++)
    {
        while(k>-1 && a[k+1]!=b[i])k=u[k];
        if(a[k+1]==b[i])k++;
        if(k==n)
        {
            nr++;
            if(nr<=1000)pos[nr]=i-k;
            k=u[k];
        }
    }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
        scanf("%s ",a);
        scanf("%s ",b);
    prefix();
    kmp();

        printf("%d\n",nr);
        for(int i=1;i<=min(1000,nr);i++)printf("%d ",pos[i]);
    return 0;
}