Cod sursa(job #318994)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 30 mai 2009 10:45:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>   
#include <string.h>   
#define dim 2000001   
  
char a[dim], b[dim], match[dim];   
int na, nb, phi[dim], ct=0;   
  
void prefix()   
{   
    int k=0, q;   
    phi[1]=0;   
    for (q=2; q<=na; q++)   
    {   
        while (k && a[k+1]!=a[q]) k=phi[k];   
        if (a[k+1]==a[q]) k++;   
        phi[q]=k;   
    }   
}   
  
void kmp()   
{   
    int q=0, i;   
    for (i=1; i<=nb; i++)   
    {   
        while (q && a[q+1]!=b[i])    
            q=phi[q];   
        if (a[q+1]==b[i]) q++;   
        if (q==na) match[i-na]=1, ct++;   
    }   
}   
  
int main()   
{   
    int i;   
    freopen("strmatch.in", "r", stdin);   
    freopen("strmatch.out", "w", stdout);   
    scanf("%s\n%s\n", a+1, b+1);   
    na=strlen(a+1);   
    nb=strlen(b+1);   
    prefix();   
    kmp();   
    printf("%d\n", ct);   
    ct=0;   
    for (i=0; i<nb && ct<1000; i++)   
        if (match[i])   
        {   
            printf("%d ", i);   
            ct++;   
        }   
    printf("\n");   
    return 0;   
}