Cod sursa(job #150274)

Utilizator MarquiseMarquise Marquise Data 6 martie 2008 20:07:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>

#define SMAX 2000001
#define RMAX 1005

int next[SMAX], r[RMAX], n, m, nr;
char s[SMAX], p[SMAX];

int main()
{
    int i, j, ex;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", p, s);
    n = strlen(s);
    m = strlen(p);
    
    j = -1;
    next[0] = -1;
    for ( i = 0; i < m; )
    {
        while ( j > -1 && p[i] != p[j])
              j = next[j];
        j++;
        i++;

        if ( p[i] == p[j])
             next[i] = next[j];
        else
             next[i] = j;          
    }

    j = 0;
    ex = 1;
    for ( i = 0; i < n && ex; )
    {
        while ( j > -1 && s[i] != p[j])
              j = next[j];
        j++;
        i++;
        if ( j >= m )
        {
           nr++;
           if ( nr <= 1000)
              r[nr] = i - j;
           j = next[j];   
         
        }      
    }
    printf("%d\n", nr);
    for ( i = 1; i <= nr && i <= 1000; i++)
        printf("%d ", r[i]);
}