Pagini recente » Cod sursa (job #53182) | Cod sursa (job #2534953) | Cod sursa (job #538713) | Cod sursa (job #3228065) | Cod sursa (job #2886777)
#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());
}
}
fout << v.size() << "\n";
int cnt = std::min((int)v.size(), 1000);
for (int it : v) {
fout << it - a.size() - 1 << " ";
cnt--;
if (cnt == 0) {
return 0;
}
}
return 0;
}