Cod sursa(job #345207)

Utilizator aghamatMorariu Razvan aghamat Data 2 septembrie 2009 10:33:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <string.h>

#define DIM 2000100

char a[DIM], b[DIM];
int pi[DIM], n, m, nr, p[1024];

void calc_pi()
{
    int k=0;
    for (int i=2; i<=n; ++i)
    {
        while (a[i]!=a[k+1] && k>0) k=pi[k];
        if (a[k+1]==a[i]) ++k;
        pi[i]=k;
    }
}

void kmp()
{
    int k=0;
    for (int i=1; i<=m; ++i)
    {
        while (a[k+1]!=b[i] && k>0) k=pi[k];
		if (a[k+1]==b[i]) ++k;
        if (k==n)
        {
            ++nr;
            if (nr<=1024) p[nr]=i-n;        
        }
    }     
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    fgets(a+1,DIM,stdin);
    fgets(b+1,DIM,stdin);
    
    while (a[++n] != '\n');--n;
    while (b[++m] != '\n');--m;
    
    calc_pi();
    kmp();
    
    printf("%d\n",nr);
    for (int i=1; i<=nr && i<=1024; ++i)
        printf("%d ",p[i]);
    printf("\n");
    return 0;
    
}