Pagini recente » Cod sursa (job #3278456) | Cod sursa (job #2931902) | Cod sursa (job #1975388) | Cod sursa (job #455686) | Cod sursa (job #3160323)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000002];
vector<int> res;
int main() {
string pattern, text;
fin >> pattern >> text;
int n = pattern.size(), m = text.size();
pi[1] = 0;
int k = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 && pattern[k] != pattern[i - 1]) {
k = pi[k];
}
if (pattern[k] == pattern[i - 1])
k++;
pi[i] = k;
}
k = 0;
for (int i = 2; i <= m; i++) {
while (k > 0 && pattern[k] != text[i - 1]) {
k = pi[k];
}
if (pattern[k] == text[i - 1])
k++;
if (k == n) {
res.push_back(i - n);
}
}
fout << res.size() << '\n';
for (auto val : res)
fout << val << ' ';
return 0;
}