Cod sursa(job #217197)

Utilizator floringh06Florin Ghesu floringh06 Data 27 octombrie 2008 17:21:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000005

char P[MAX_N]; // pattern
char T[MAX_N];

int U[MAX_N];
int S[1010];
int N, M;

    void prefix ()
    {
        int k = 0;
        int i;

        U[0] = 0;
        for (i = 2; i <= M; ++i)
        {
            while (k > 0 && P[k + 1] != P[i]) k = U[k];
            if (P[k + 1] == P[i]) ++k;

            U[i] = k;
        }
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);

        scanf ("%s", P + 1);
        scanf ("%s", T + 1);
        M = strlen (P + 1);
        N = strlen (T + 1);

        prefix ();

        int cnt = 0, k = 0, i;

        for (i = 1; i <= N; ++i)
        {
            while (k > 0 && P[k + 1] != T[i]) k = U[k];
            if (P[k + 1] == T[i]) ++k;

            if (k == M) 
            {
                  ++cnt;
                  if ( cnt <= 1000 )      
                   S[cnt] = i - M;     
            }
        }
        printf ("%d\n", cnt);
        for (i = 1; i <= cnt && i <= 1000; ++i) printf ("%d ", S[i]);   

        return 0;
    }