Cod sursa(job #161487)

Utilizator tm_raduToma Radu tm_radu Data 18 martie 2008 11:52:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <string.h>

int n, m;
char s1[2000001], s2[2000001];
int p[2000002];
int nrsol;
int o[2000001];
int i, j, k;

void Prefix();

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", &s1, &s2);
    n = strlen(s1);
    m = strlen(s2);
    Prefix();
    k = 0;
    for ( i = 0; i < m; i++ )
    {
        while ( k > 0 && s1[k] != s2[i] )
            k = p[k];
        if ( s1[k] == s2[i] ) k++;
        if ( k == n )
        {
            nrsol++;
            o[nrsol] = i-n+1;
        }
    }
    printf("%d\n", nrsol);
    for ( i = 1; i < nrsol; i++ )        
        printf("%d ", o[i]);
    printf("%d\n", o[nrsol]);
    
    return 0;
}

void Prefix()
{
    p[1] = 0; k = 0;    
    for ( i = 1; i < n; i++ )
    {
        while ( k > 0 && s1[k] != s1[i] )
            k = p[k];
        if ( s1[k] == s1[i] ) k++;
        p[i+1] = k;
    }
}