Cod sursa(job #1414773)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 2 aprilie 2015 23:50:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

#include <cstring>
using namespace std;

const int MAX_N = 2000005;

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

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    A[0] = B[0] = T[0] = ' ';
    f >> (A + 1);
    f >> (B + 1);

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

    for(int i = 1; i <= N; ++i) {
        T[i] = A[i];
    }

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

    for(int i = 1; i <= M; ++i) {
        T[++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(i + z[i] - 1 <= L && T[i + z[i]] == T[z[i] + 1]) {
            ++z[i];
        }

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

    g << ans << "\n";
    for(int i = 1; i <= ans; ++i) {
        g << sol[i] << " ";
    }
    g << "\n";

    f.close();
    g.close();

    return 0;
}