Pagini recente » Cod sursa (job #897585) | Cod sursa (job #1609413) | Cod sursa (job #1218898) | Cod sursa (job #2361817) | Cod sursa (job #1678618)
#include <fstream>
#include <algorithm>
#include <cstring>
#define NMAX 2000005
#define lim 1000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i, n, m, j, k = 0, pi[NMAX], ans[lim + 3], cnt = 0, sol[lim + 3];
char a[NMAX], b[NMAX];
int main()
{
f.getline(a, NMAX - 3);
n = strlen(a);
for (i = n; i >= 1; -- i)
a[i] = a[i - 1];
f.getline(b, NMAX - 3);
m = strlen(b);
for (i = m; i >= 1; -- i)
b[i] = b[i - 1];
pi[1] = 0;
for (i = 2; i <= n; ++ i)
{
while (k > 0 && a[i] != a[k + 1])
k = pi[k];
if (a[k + 1] == a[i])
k ++;
pi[i] = k;
}
k = 0;
for (i = 1; i <= m; ++ i)
{
while (k > 0 && b[i] != a[k + 1])
k = pi[k];
if (b[i] == a[k + 1])
k ++;
if (k == n)
{
ans[++ cnt] = i - n;
if (cnt == lim - 1)
break;
}
}
g << cnt << '\n';
for (i = 1; i<= cnt; ++ i)
g << ans[i] << " ";
return 0;
}