Cod sursa(job #1373343)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 4 martie 2015 18:10:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<fstream>
#include<iostream>
using namespace std;

const int kLMax = 2000005, kSMax = 1010;
char a[kLMax], b[kLMax];
int n, m, q, pi[kLMax];
int sol, poz[kSMax];

void Citire() {
    ifstream in ("strmatch.in");
    int i;
    in.getline(a, kLMax);
    in.getline(b, kLMax);
    for (i = 0; a[i] >= '0' && a[i] <= 'z'; ++i);
    m = i;
    for (i = 0; b[i] >= '0' && b[i] <='z'; ++i);
    n = i;

    for (i = m; i >= 1; --i)
        a[i] = a[i-1];
    a[0] = ' ';
    for (i = n; i >= 1; --i)
        b[i] = b[i-1];
    b[0] = ' ';

    in.close();
}

void Prefix() {
    pi[1] = 0;
    for (int i = 2; i <= m; ++i) {
        while (q && a[q + 1] != a[i])
            q = pi[q];
        if (a[q + 1] == a[i])
            ++q;
        pi[i] = q;
    }
}

void Solve() {
    Prefix();
    q = 0;
    for (int i = 1; i <= n; ++i) {
        while (q && a[q+ 1] != b[i])
            q = pi[q];
        if (a[q + 1] == b[i])
            q++;
        if(q == m) {
            q = pi[m];
            ++sol;
            if (sol <= 1000)
                poz[sol] = i - m;
        }
    }
}

void Afisare() {
    ofstream out("strmatch.out");
    out << sol << '\n';
    sol = min(sol, 1000);
    for (int i = 1; i <= sol; ++i)
        out << poz[i] << ' ';
    out << '\n';
    out.close();
}

int main () {
    Citire();
    Solve();
    Afisare();
    return 0;
}