Cod sursa(job #2480861)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 26 octombrie 2019 10:44:13
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#include <algorithm>

using namespace std;

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

const int MAXN = 2000001, MAXS = 1000;
char sub[MAXN], str[MAXN];
int len[MAXN], sol[MAXN], n, m, k;

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

void preprocess() {
    len[1] = 1;
    for (int i = 2, j = 1; i <= m;) {
        if (sub[i] == sub[j])
            len[i++] = ++j;
        else if (j == 1)
            len[i++] = 1;
        else
            j = len[i - 1];
    }
}

void solve() {
    for (int i = 1, j = 1; i <= n;) {
        if (str[i] == sub[j]) {
            if (j == m) {
                if (k < MAXS)
                    sol[k] = i - j;
                ++k;
                j = len[j];
            }
            else
                ++j;
            ++i;
        }
        else if (j == 1)
            ++i;
        else
            j = len[j - 1];
    }
}

void print() {
    fout << k << '\n';
    k = min(k, MAXS);
    for (int i = 0; i < k; ++i)
        fout << sol[i] << ' ';
}

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