Cod sursa(job #250794)

Utilizator crawlerPuni Andrei Paul crawler Data 31 ianuarie 2009 20:51:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2000100

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

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    fgets(a+1,Nmax,stdin);
    fgets(b+1,Nmax,stdin);
    
    while (a[++n] != '\n');--n;
    while (b[++m] != '\n');--m;
   
    int tmp=0;
    for (int i=2;i<=n;++i)
    {
        while (a[i] != a[tmp+1] && tmp > 0) tmp = pi[tmp];
        if (a[tmp+1] == a[i]) ++tmp;
        pi[i] = tmp;   
    }
    
    tmp=0;
    for (int i=1;i<=m;++i)
    {
        while (tmp > 0 && a[tmp+1] != b[i]) tmp = pi[tmp];
        if (a[tmp+1] == b[i]) ++tmp;
        if (tmp == n)
        {
            ++nr;
            if (nr<=1000) p[nr] = i-n;    
        }    
    }
    
    printf("%d\n", nr);
    
    for (int i=1;i<=nr && i<=1000;++i)
    printf("%d ", p[i]);
    
    printf("\n");
    
    
    return 0;    
}