Pagini recente » Cod sursa (job #514562) | Cod sursa (job #297747) | Cod sursa (job #2778173) | Cod sursa (job #2630493) | Cod sursa (job #3226911)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2e6;
string a, b;
int kmp[2 * NMAX + 1];
void solve() {
fin >> a >> b;
int sz = a.length();
a = a + "#" + b;
for (int i = 1; i < a.length(); i++) {
int j = kmp[i - 1];
while (j > 0 && a[i] != a[j])
j = kmp[j - 1];
if (a[i] == a[j])
j++;
kmp[i] = j;
}
int ans = 0;
vector<int> pos;
for (int i = 1; i < a.length(); i++) {
if (kmp[i] == sz) {
ans++;
if (ans <= 1000)
pos.push_back(i - 2 * sz);
}
}
fout << ans << '\n';
for (int & x : pos)
fout << x << ' ';
}
signed main() {
solve();
return 0;
}