Cod sursa(job #2040171)

Utilizator Alex18maiAlex Enache Alex18mai Data 15 octombrie 2017 14:20:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string s, one, two;
vector<int> z(4000100);
vector<int> pos;

void make_s() {
    cin >> one >> two;
    s += ' ';
    s += one;
    s += '#';
    s += two;
}

void solve() {

    int cont = 0;

    int op = 0;

    int C = 0, R = 0;
    for (int i = 1; i < s.size(); i++) {
        z[i] = max(min(z[i - C], R - i), 0);
        while (s[z[i] + 1] == s[i + z[i] + 1]) {
            op++;
            z[i]++;
        }
        if (z[i] == one.size()) {
            cont++;
            if (cont <= 1000) {
                pos.push_back(i - one.size() - 1);
            }
        }
        if (R < i + z[i]){
            R = i + z[i];
            C = i;
        }
    }

    cout << cont << '\n';
    for (auto &x : pos) {
        cout << x << " ";
    }
}

int main() {

    make_s();

    solve();

    return 0;
}