Cod sursa(job #935498)

Utilizator mvcl3Marian Iacob mvcl3 Data 3 aprilie 2013 16:46:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
#define NMAX 2000009
using namespace std;

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

char A[NMAX], B[NMAX], aux[NMAX];
int n, m, pi[NMAX];
int nr, sol[NMAX];

inline void pre() {
    int k = 0;
    pi[1] = 0;
    for(int q = 2; q <= m; ++q) {
        while(k > 0 && B[k + 1] != B[q])
            k = pi[k];
        if(B[k + 1] == B[q]) ++ k;
        pi[q] = k;
    }
}

int main() {
    f.getline(B, NMAX);
    f.getline(A, NMAX);
    m = strlen(B), n = strlen(A);
    for(int i = n; i >= 1; -- i) A[i] = A[i - 1];
    for(int i = m; i >= 1; -- i) B[i] = B[i - 1];

    pre();

    int q = 0;
    for(int i = 1; i <= n; ++i) {
        while(q > 0 && B[q + 1] != A[i])
            q = pi[q];
        if(B[q + 1] == A[i])
            ++ q;
        if(q == m)
        {
            sol[ ++ sol[0]] = i - m;
            if(sol[0] > 1000) break;
        }
    }

    g << sol[0] << '\n';
    for(int i = 1; i <= sol[0]; ++i) g << sol[i] << ' ';
    g << '\n';
    g.close();
    return 0;
}