Cod sursa(job #1967070)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 15 aprilie 2017 21:02:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

string pat, str, cat;
vector<int> aps;
int ant;

int z[1 << 21];

void make_z(const string &str, int z[]) {
    int n = str.size();
    for (int l, i = 1, r = 0; i < n; ++i) {
        if (i > r) {
            for (l = r = i; str[r - l] == str[r]; ++r);
            z[i] = r - l;
            --r; }
        else {
            z[i] = min(z[i - l], r - i + 1);
            if (i + z[i] >= r) {
                for (l = i; str[r - l] == str[r]; ++r);
                z[i] = r - i;
                --r; } } } }

int main() {
    fi >> pat >> str;
    cat = pat + "#" + str;

    make_z(cat, z);

    for (int i = 0; i < cat.size(); ++i)
        if (z[i] >= pat.size())
            if (++ant <= 1000)
                aps.push_back(i - pat.size() - 1);

    fo << ant << '\n';
    for (auto i: aps)
        fo << i << ' ';
    fo << '\n';

    return 0; }