Pagini recente » Cod sursa (job #69688) | Cod sursa (job #1933952) | Cod sursa (job #628095) | Cod sursa (job #2525747) | Cod sursa (job #2716472)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int LMAX = 2e6;
char a[LMAX + 2], b[LMAX + 2];
int pi[LMAX + 1];
vector<int> ans;
int main() {
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, m;
in >> (a + 1) >> (b + 1);
m = strlen(a + 1), n = strlen(b + 1);
int lung;
pi[1] = lung = 0;
for (int i = 2; i <= m; ++i) {
while (lung > 0 && a[i] != a[lung + 1])
lung = pi[lung];
if (a[i] == a[lung + 1])
++lung;
pi[i] = lung;
}
lung = 0;
for (int i = 1; i <= n; ++i) {
while (lung > 0 && b[i] != a[lung + 1])
lung = pi[lung];
if (b[i] == a[lung + 1])
++lung;
if (lung == m)
ans.push_back(i - lung);
}
if (ans.size() > 1000) {
out << "1000\n";
for (int i = 0; i < 1000; ++i)
out << ans[i] << ' ';
}
else {
out << ans.size() << '\n';
for (auto i : ans)
out << i << ' ';
}
in.close();
out.close();
}