Cod sursa(job #2482721)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 28 octombrie 2019 19:37:43
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int MAXS = 2e6 + 10, MAXN = 1e4;
char sub[MAXS], str[MAXS];
int len[MAXS], pos[MAXN], n, m, k;

void read() {
    fin.getline(sub + 1, MAXS);
    fin.getline(str + 1, MAXS);
    m = strlen(sub + 1);
    n = strlen(str + 1);
}

void preprocess() {
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && sub[j + 1] != sub[i])
            j = pos[j];
        if (sub[j + 1] == sub[i])
            len[i] = ++j;
    }
}

void kmp() {
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && sub[j + 1] != str[i])
            j = pos[j];
        if (sub[j + 1] == str[i]) {
            ++j;
            if (j == m) {
                if (k < 1000)
                    pos[k] = i - j;
                ++k;
                j = len[j];
            }
        }
    }
}

void print() {
    fout << k << '\n';
    if (k > 1000)
        k = 1000;
    for (int i = 0; i < k; ++i)
        fout << pos[i] << ' ';
}

int main() {
    read();
    preprocess();
    kmp();
    print();
    return 0;
}