Pagini recente » Cod sursa (job #450896) | Istoria paginii runda/fmimorarcosmin2012 | Cod sursa (job #2007711) | Cod sursa (job #1391868) | Cod sursa (job #2573094)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define input "strmatch.in"
#define output "strmatch.out"
const int lMax = 2000003;
using namespace std;
char a[lMax], b[lMax];
int n, m, k, q, ans1;
int pi[lMax];
int ans2[1001];
main()
{
freopen(input, "rt", stdin);
freopen(output, "wt", stdout);
cin >> a + 1 >> b + 1;
n = strlen(a + 1);
m = strlen(b + 1);
k = 0;
pi[1] = 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;
}
q = 0;
for (int i = 1; i <= m; ++i)
{
while (q && a[q + 1] != b[i])
q = pi[q];
if (a[q + 1] == b[i])
++q;
if (q == n)
{
ans2[++ans1] = i - n;
}
}
cout << ans1 << "\n";
for (int i = 1; i <= min(ans1, 1000); ++i)
cout << ans2[i] << " ";
return 0;
}