Cod sursa(job #855887)

Utilizator deneoAdrian Craciun deneo Data 15 ianuarie 2013 19:29:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define MAXN 2100000

int N, M, prefix[MAXN], v[MAXN];
char A[MAXN], B[MAXN];

void doPrefix() {
    prefix[1] = 0;

    for (int i = 2, p = 0; i <= M; ++i) {
        while (p > 0 && A[i] != A[p + 1])
            p = prefix[p];
        if (A[i] == A[p + 1])
            ++p;
        prefix[i] = p;
    }
}

int main() {
    fin.getline(A + 1, MAXN);
    fin.getline(B + 1, MAXN);

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

    doPrefix();

    for (int i = 1, j = 0; i <= N; ++i) {
        while (j > 0 && B[i] != A[j + 1])
            j = prefix[j];
        if (B[i] == A[j + 1])
            ++j;
        if (j == M && v[0] < 1000)
            v[++v[0]] = i - M;
    }

    fout << v[0] << "\n";
    for (int i = 1; i <= v[0]; ++i)
        fout << v[i] << " ";

    return 0;
}