Pagini recente » Cod sursa (job #1081101) | Cod sursa (job #3356237) | Cod sursa (job #761293) | Cod sursa (job #2294740) | Cod sursa (job #3357337)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 4e6 + 5;
int kmp[NMAX];
int main() {
string a, b;
fin >> a >> b;
string s = a + '#' + b;
for (int i = 1; i < s.size(); i++) {
int x = kmp[i - 1];
while (x > 0 && s[i] != s[x])
x = kmp[x - 1];
if (s[i] == s[x])
x++;
kmp[i] = x;
}
vector<int> ans;
for (int i = a.size() + 1; i < s.size(); i++) {
if (kmp[i] == a.size()) {
int poz = i - 2 * a.size();
if (ans.size() < 1000)
ans.push_back(poz);
}
}
fout << ans.size() << '\n';
for (auto it : ans) {
fout << it << ' ';
}
return 0;
}