Pagini recente » Cod sursa (job #2505080) | Cod sursa (job #2340726) | Cod sursa (job #1274778) | Cod sursa (job #1621861) | Cod sursa (job #2279075)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int maxn = 2 * 1e6;
const int maxr = 1000;
char a[maxn + 2], b[maxn + 2];
int n, m, ans, pi[maxn + 1], pos[maxr + 1];
int main()
{
fi >> (a + 1) >> (b + 1);
int k;
n = strlen(a + 1);
m = strlen(b + 1);
pi[ 1 ] = 0;
k = 0;
for (int i = 2; i <= n; i++) {
while (k && a[k + 1] != a[ i ])
k = pi[ k ];
if (a[k + 1] == a[ i ])
k++;
pi[ i ] = k;
}
k = 0;
for (int i = 1; i <= m; i++) {
while (k && a[k + 1] != b[ i ])
k = pi[ k ];
if (a[k + 1] == b[ i ])
k++;
if (k == n) {
ans++;
if (ans <= maxr)
pos[ans] = i;
}
}
fo << ans << '\n';
for (int i = 1; i <= min(ans, maxr); i++) {
fo << pos[ i ] - n << ' ';
}
fo.close();
fi.close();
return 0;
}