Cod sursa(job #1745972)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 22 august 2016 16:26:28
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;

const int SMAX = 2000005;

char a[SMAX],
     b[SMAX];
int pi[SMAX];

int rez[1001];

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

    int i, k, r, n, m, s;

    gets(a + 1);
    gets(b + 1);

    n = strlen( a + 1 );
    m = strlen( b + 1 );
    n -= ( a[n] == '\n' );
    m -= ( a[m] == '\n' );

    pi[0] = -1;
    k = r = s = 0;
    for ( i = 1; i <= m; i ++ ) {
        while ( k != -1 && b[i] != a[k + 1] )
            k = pi[k];

        k ++;
        pi[i] = k;

        if ( k == n ) {
            if ( s < 1000 )
                rez[s] = i - n;
            s ++;
        }
    }

    printf( "%d\n", s );
    for ( i = 0; i < s && i < 1000; i ++ )
        printf( "%d ", rez[i] );

    return 0;
}