Pagini recente » Cod sursa (job #589533) | Cod sursa (job #2894841) | Cod sursa (job #1551751) | Cod sursa (job #936543) | Cod sursa (job #2833847)
#include <fstream>
const int MAX_N = 2 * 1e6;
int kmp[1 + 2 * MAX_N + 1];
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 (b[l] != b[i - 1] && l > 0) {
l = kmp[l];
}
if (b[l] == b[i - 1]) {
kmp[i] = l + 1;
} else {
kmp[i] = 0;
}
}
int cnt = 0;
for (int i = 1; i <= b.size(); i++) {
if (kmp[i] == a.size()) {
cnt++;
}
}
fout << cnt << "\n";
cnt = std::min(cnt, 1000);
for (int i = 1; i <= b.size() && cnt; i++) {
if (kmp[i] == a.size()) {
fout << i - 2 * a.size() - 1 << " ";
cnt--;
}
}
return 0;
}