Cod sursa(job #1456022)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 iunie 2015 17:45:10
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
/*
    Strmatch using Z-Algorithm
      Coded by: "Emanuel Nrx"
*/
#include <cstdio>
#include <cstring>
#define DIM 2097152
using namespace std;

int Z[DIM*2], L, R, P[1001], R2, L2, N, M, i, j, nr, val, K;
char S[DIM*2], A[DIM], B[DIM];

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[1] = N + M;
    for(int i = 2; i <= N + M; i ++){
        if(S[i] != S[1]){
            if(i > R){
                L = 0;
                R = 0;
            }
            Z[i] = 0;
        }
        else{
            if(S[i] > R){
                L = i;
                R = i;
                while(S[R-L+2] == S[R+1])
                    R ++;
                Z[i] = R - L + 1;
            }
            else{
                if(i + Z[i] < R){
                    Z[i] = Z[i-L+1];
                    L = L;
                    R = R;
                }
                else{
                    L = i;
                    R = R;
                    while(S[R-L+2] == S[R+1])
                        R ++;
                    Z[i] = R - L + 1;
                }
            }
        }
        if(Z[i] >= N && i > N && nr < 1000)
            P[++nr] = i - N - 1;
    }

    printf("%d\n", nr);
    for(int i = 1; i <= nr; i ++)
        printf("%d ", P[i]);

    fclose(stdin );
    fclose(stdout);

    return 0;
}