Cod sursa(job #145380)

Utilizator floringh06Florin Ghesu floringh06 Data 28 februarie 2008 19:24:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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[1010];

int n, m;
int cnt;

    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 i;
        for ( int k = 0, i = 1; i <= n; ++i )   
        {   
            while ( k && 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;
    }