Cod sursa(job #1456111)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 iunie 2015 19:50:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <cstring>
using namespace std;

const int DIM = (1<<21);

int N, M, i, j, k, k2, R, L;
int Z[DIM*2], Sol[2048], nr;
char A[DIM], B[DIM], S[DIM*2];

int main(){

    freopen("strmatch.in" ,"r", stdin );
    freopen("strmatch.out","w", stdout);

    scanf("%s", A + 1); N = strlen(A + 1);
    scanf("%s", B + 1); M = strlen(B + 1);

    for(int i = 1; i <= N; i ++)
        S[i+0] = A[i];

    for(int i = 1; i <= M; i ++)
        S[i+N] = B[i];

    Z[0] = N;

    for(int i = 2; i <= N + M; i ++){

        if(i > R){

            int j = 1;

            while(S[j] == S[i+j-1])
                j ++;

            Z[i] = j - 1;
            L = i;
            R = L + Z[i] - 1;

        }
        else {

            int K = i - L + 1;

            if(Z[K] < R - i + 1){

                Z[i] = Z[K];

            }
            else {

                int j = Z[K];

                while(S[j] == S[i+j-1])
                    j ++;

                Z[i] = j - 1;
                L = i;
                R = L + Z[i] - 1;
            }

        }

        if(Z[i] >= N && i > N){

            nr ++;

            if(nr <= 1000)
                Sol[nr] = i - Z[i] - 1;
        }

    }

    printf("%d\n", nr);

    for(int i = 1; i <= nr && i <= 1000; i ++)
        printf("%d ", Sol[i]);

    fclose(stdin );
    fclose(stdout);

    return 0;
}