Pagini recente » Cod sursa (job #841170) | Cod sursa (job #682257) | Cod sursa (job #1899130) | Cod sursa (job #2161079) | Cod sursa (job #2886775)
#include <fstream>
#include <vector>
const int MAX_N = 2 * 1e6;
int kmp[1 + 2 * MAX_N];
std::vector<int> v;
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string a, b;
fin >> a >> b;
b = a + "$" + b;
kmp[1] = 0;
for (int i = 2; i <= b.size(); i++) {
int l = kmp[i - 1];
while (l > 0 && b[i - 1] != b[l]) {
l = kmp[l];
}
if (b[i - 1] != b[l]) {
kmp[i] = 0;
} else {
kmp[i] = l + 1;
}
}
for (int i = 1; i <= b.size(); i++) {
if (kmp[i] == a.size()) {
v.push_back(i - a.size());
if (v.size() == 1000) {
break;
}
}
}
fout << v.size() << "\n";
for (int it : v) {
fout << it - a.size() - 1 << " ";
}
return 0;
}