Cod sursa(job #356132)

Utilizator floringh06Florin Ghesu floringh06 Data 13 octombrie 2009 17:05:10
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

char P[MAX_N], C[MAX_N];

int U[MAX_N], S[1 << 10];
int N, M;

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