#include <bits/stdc++.h>
using namespace std;
vector<int> compute_pi(string pat) {
int n = pat.length();
vector<int> pi(n);
pi[0] = 0;
for (int i = 1; i < n; i++) {
pi[i] = 0;
int j = pi[i - 1]; /* trying length j + 1 */
while (j > 0 && pat[j] != pat[i]) {
j = pi[j - 1];
}
if (pat[j] == pat[i]) {
pi[i] = j + 1;
}
}
return pi;
}
vector<int> find_matches(string text, string pat) {
int n = pat.length(), m = text.length();
string s = pat + "$" + text;
vector<int> pi = compute_pi(s), ans;
for (int i = n + 1; i <= n + m; i++) { /* n + 1 is where the text starts */
if (pi[i] == n) {
ans.push_back(i - 2 * n); /* i - (n - 1) - (n + 1) */
}
}
return ans;
}
int main() {
string abc = "abcabcb";
vector<int> ans = compute_pi(abc);
for(int i = 0 ; i < ans.size() ; i++) {
cout << abc[i] << " " << ans[i] << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKdmVjdG9yPGludD4gY29tcHV0ZV9waShzdHJpbmcgcGF0KSB7CiAgaW50IG4gPSBwYXQubGVuZ3RoKCk7CiAgdmVjdG9yPGludD4gcGkobik7CiAgcGlbMF0gPSAwOwogIGZvciAoaW50IGkgPSAxOyBpIDwgbjsgaSsrKSB7CiAgICBwaVtpXSA9IDA7CiAgICBpbnQgaiA9IHBpW2kgLSAxXTsgLyogdHJ5aW5nIGxlbmd0aCBqICsgMSAqLwogICAgd2hpbGUgKGogPiAwICYmIHBhdFtqXSAhPSBwYXRbaV0pIHsKICAgICAgaiA9IHBpW2ogLSAxXTsKICAgIH0KICAgIGlmIChwYXRbal0gPT0gcGF0W2ldKSB7CiAgICAgIHBpW2ldID0gaiArIDE7CiAgICB9CiAgfQogIHJldHVybiBwaTsKfQoKdmVjdG9yPGludD4gZmluZF9tYXRjaGVzKHN0cmluZyB0ZXh0LCBzdHJpbmcgcGF0KSB7CiAgaW50IG4gPSBwYXQubGVuZ3RoKCksIG0gPSB0ZXh0Lmxlbmd0aCgpOwogIHN0cmluZyBzID0gcGF0ICsgIiQiICsgdGV4dDsKICB2ZWN0b3I8aW50PiBwaSA9IGNvbXB1dGVfcGkocyksIGFuczsKICBmb3IgKGludCBpID0gbiArIDE7IGkgPD0gbiArIG07IGkrKykgeyAvKiBuICsgMSBpcyB3aGVyZSB0aGUgdGV4dCBzdGFydHMgKi8KICAgIGlmIChwaVtpXSA9PSBuKSB7CiAgICAgIGFucy5wdXNoX2JhY2soaSAtIDIgKiBuKTsgLyogaSAtIChuIC0gMSkgLSAobiArIDEpICovCiAgICB9CiAgfQogcmV0dXJuIGFuczsKfQoKaW50IG1haW4oKSB7CglzdHJpbmcgYWJjID0gImFiY2FiY2IiOyAKCXZlY3RvcjxpbnQ+IGFucyA9IGNvbXB1dGVfcGkoYWJjKTsKCWZvcihpbnQgaSA9IDAgOyBpIDwgYW5zLnNpemUoKSA7IGkrKykgewoJY291dCA8PCBhYmNbaV0gPDwgIiAiIDw8IGFuc1tpXSA8PCBlbmRsOwp9IAoJcmV0dXJuIDA7Cn0=