Pagini recente » Cod sursa (job #511886) | Cod sursa (job #730501) | Cod sursa (job #1019012) | Cod sursa (job #2522806) | Cod sursa (job #3160327)
#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 (int i = 0; i < min(999, (int)res.size()); i++)
fout << res[i] << ' ';
return 0;
}