Cod sursa(job #145342)

Utilizator floringh06Florin Ghesu floringh06 Data 28 februarie 2008 18:59:57
Problema Potrivirea sirurilor Scor 40
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

int U[MAX_N];
char T[MAX_N], P[MAX_N];
int S[1005];

int n, m;
int cnt;

    void prefix ()
    {
         int k = -1;
         int i;
         
         U[0] = 0;
         for (i = 1; 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);
        
        gets (P); 
        gets (T);
        m = strlen (P); n = strlen (T);
        
        prefix ();
        int i;
        int x = -1;
        
        for (i = 0; i < n; ++i)
        {
            while (x > 0 && P[x + 1] != T[i]) x = U[x];
            if (P[x + 1] == T[i]) ++x;
            if (x == m - 1)
            {
               x = U[x];
               if (cnt < 1005)
                  S[++cnt] = i - m + 1;
            }
        }
        
        printf ("%d\n", cnt);
        for (i = 1; i <= cnt && i <= 1000; ++i) printf ("%d ", S[i]);
        
        return 0;
    }