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