Cod sursa(job #2372856)

Utilizator AndoneAlexandruAndone Alexandru AndoneAlexandru Data 7 martie 2019 11:21:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
using namespace std;

char a[2000005];
char b[2000005];
int p[2000005];
int m;

void form_prefix() {
    m = strlen(a+1);
    int i = 0;
    p[1] = 0;
    for (int j = 2; j <= m; ++j) {
        while (i > 0 && a[i+1] != a[j])
            i = p[i];
        if (a[i+1] == a[j])
            ++i;
        p[j] = i;
    }
}

int n, nr;
int afis[1005];

void str_matching() {
    int n = strlen(b+1);
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        while (k != 0 && b[i] != a[k+1])
            k = p[k];
        if (b[i] == a[k+1])
            k++;
        if (k == m) {
            nr++;
            if (nr <= 1000)
                afis[nr] = i - m;
            k = p[k];
        }
    }
}

int main() {
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in.getline(a+1, 2000005);
    in.get(b+1, 2000005);
    form_prefix();
    str_matching();
    int aa = nr;
    out << aa << '\n';
    if (aa > 1000) aa = 1000;
    for (int i = 1; i <= aa; ++i)
        out << afis[i] << " ";
    return 0;
}