Cod sursa(job #288338)

Utilizator raula_sanChis Raoul raula_san Data 25 martie 2009 18:43:37
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstring>

#define MAX_L 2000002
#define MAX_S 1001

using namespace std;

int C, N, M, Pi[MAX_L], Sol[MAX_S];
char A[MAX_L], B[MAX_L];

void Prefix()
{
     int k = 0, i;
     
     Pi[1] = 0;
     for ( i = 2; i <= N; ++i )
     {
         while(k > 0 && A[k+1] != A[i])
                 k = Pi[k];
                 
         if(A[k+1] == A[i])
                 ++ k;
                 
         Pi[i] = k;
     }
}

int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    
    scanf("%s", A);
    scanf("%s", B);
    N = strlen(A);
    M = strlen(B);

    int q = 0, i;

    for ( i = N; i; --i )
        A[i] = A[i-1];
    
    A[0] = ' ';
    
    for ( i = M; i; --i )
    
    Prefix();
    
    for ( i = 1; i <= M; ++i )
    {
        while(q > 0 && A[q+1] != B[i])
                q = Pi[q];
                
        if(B[i] == A[q+1])
                ++ q;
                
        if(q == N)
        {
             q = Pi[q];
             ++ C;
             
             if(C <= 1000)
                  Sol[++Sol[0]] = i - N + 1;
        }
    }

    printf("%d\n", C);
    
    for ( i = 1; i <= Sol[0]; ++i )
        printf("%d ", Sol[i]);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}