Pagini recente » Cod sursa (job #2430066) | Cod sursa (job #572051) | Cod sursa (job #2415976) | Cod sursa (job #609972) | Cod sursa (job #1871668)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string pattern, text;
vector<int> ans;
cin >> pattern >> text;
vector<int> lps(pattern.size());
int i = 1;
int j = 0;
while (i < pattern.size()) {
if (pattern[i] == pattern[j]) {
lps[i] = j + 1;
++i, ++j;
} else {
if (j == 0) {
lps[i] = 0;
++i;
} else {
j = lps[j - 1];
}
}
}
i = 0, j = 0;
while (i < text.size() && j < pattern.size()) {
if (text[i] == pattern[j]) {
++i, ++j;
} else {
if (j == 0) {
++i;
} else {
j = lps[j - 1];
}
}
if (j == pattern.size()) {
ans.push_back(i - pattern.size());
j = lps[j - 1];
}
}
cout << ans.size() << '\n';
for (int x : ans) {
cout << x << ' ';
}
return 0;
}