Pagini recente » Cod sursa (job #1746769) | Cod sursa (job #1497729) | Cod sursa (job #192786) | Cod sursa (job #1583058) | Cod sursa (job #2470440)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))
using namespace std;
const int MAXN = (int) 2e6;
char a[2 * MAXN + 1], b[MAXN + 1];
int z[2 * MAXN + 1];
int main() {
#if 0
ifstream cin("A.in");
ofstream cout("A.out");
#endif
int i;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> a + 1 >> b;
int n = strlen(a + 1), m = strlen(b);
for(i = 0; i < m; i++) {
a[i + n + 1] = b[i];
}
z[1] = n + m;
int pos = 0;
for(i = 2; i <= n + m; i++) {
if(pos + z[pos] >= i) {
z[i] = min(pos + z[pos] - i, z[i - pos + 1]);
}
while(i + z[i] <= n + m && a[i + z[i]] == a[z[i] + 1]) {
z[i]++;
}
if(pos + z[pos] < i + z[i]) {
pos = i;
}
}
vector <int> sol;
int ans = 0;
for(i = n + 1; i <= n + m; i++) {
if(z[i] >= n) {
ans++;
if(sol.size() < 1000) {
sol.push_back(i - n - 1);
}
}
}
for(i = 1; i <= n + m; i++) {
cerr << a[i];
}
cerr << "\n";
for(i = 1; i <= n + m; i++) {
cerr << z[i] << " ";
}
cerr << "\n";
cout << ans << "\n";
for(auto it : sol) {
cout << it << " ";
}
return 0;
}