Cod sursa(job #1414792)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 aprilie 2015 00:13:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = 2000005;

int N, M, ans;
int z[2 * MAX_N], sol[1002];
char A[2 * MAX_N], B[MAX_N];

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

    A[0] = B[0] = ' ';
    fgets(A + 1, MAX_N - 2, stdin);
    fgets(B + 1, MAX_N - 2, stdin);

    N = strlen(A) - 2;
    M = strlen(B) - 2;


    int L = N;
    A[++L] = '#';

    for(int i = 1; i <= M; ++i) {
        A[++L] = B[i];
    }

    for(int i = 2, C = 0, R = 0; i <= L; ++i) {
        if(R >= i) {
            z[i] = min(z[i - C + 1], R - i + 1);
        }

        while(A[i + z[i]] == A[z[i] + 1] && i + z[i] <= L) {
            ++z[i];
        }

        if(i + z[i] - 1 > R) {
            C = i;
            R = i + z[i] - 1;
        }
    }

    for(int i = N + 2; i <= L; ++i) {
        if(z[i] == N) {
            ++ans;
            if(ans <= 1000) {
                sol[ans] = i - N - 2;
            }
        }
    }

    printf("%d\n", ans);
    for(int i = 1; i <= min(ans, 1000); ++i) {
        printf("%d ", sol[i]);
    }
    printf("\n");

    fclose(stdin);
    fclose(stdout);

    return 0;
}