Cod sursa(job #1966875)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 15 aprilie 2017 17:07:51
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 1 << 21;

vector<int> aps;
string a, b, c1, c2;
int n, m, q, apps;

int z[NMAX];

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

int main() {
    string str, pat;

    fi >> pat >> str;
    str = pat + "#" + str;

    make_z(str, z);
    for (int i = 1; i < str.size(); ++i)
        if (z[i] == pat.size()) {
            ++apps;
            if (apps <= 1000)
                aps.push_back(i - pat.size() - 1); }

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

    return 0; }