Cod sursa(job #2045414)

Utilizator retrogradLucian Bicsi retrograd Data 22 octombrie 2017 13:00:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> ComputePi(string s) {
    int n = s.size();
    vector<int> pi(n + 1, -1);
    for (int i = 0; i < n; ++i) {
        int j = pi[i];
        while (j != -1 && s[j] != s[i - 1]) j = pi[j];
        pi[i + 1] = j + 1;
    }
    return pi;
}

vector<int> Match(string text, string pat) {
    auto pi = ComputePi(pat);
    vector<int> ret;
    int j = -1;

    for (int i = 0; i < (int)text.size(); ++i) {
        while (j != -1 && pat[j] != text[i]) j = pi[j];
        if (++j == pat.size()) 
            ret.push_back(i), j = pi[j]; 
    }
    return ret;
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    string text, pat; cin >> pat >> text;
    auto matches = Match(text, pat);
    cout << matches.size() << endl;
    for (int i = 0; i < (int)matches.size() && i < 1000; ++i)
        cout << matches[i] - pat.size() + 1 << " ";
    cout << endl;
}