Pagini recente » Cod sursa (job #2382305) | Cod sursa (job #2474079) | Cod sursa (job #199899) | Cod sursa (job #1648239) | Cod sursa (job #1644830)
#include <fstream>
#include <cstring>
#define NMAX 200005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i, n, m, k, p[NMAX], ans[NMAX], cont = 0;
char a[NMAX], b[NMAX];
void make_prefix()
{
k = 0;
for (i = 2; i <= n; ++ i)
{
while (k > 0 && a[k + 1] != a[i])
k = p[k];
if (a[k + 1] == a[i])
k ++;
p[i] = k;
}
}
int main()
{
f.getline(a + 1, NMAX - 3);
f.getline(b + 1, NMAX - 3);
n = strlen(a + 1);
m = strlen(b + 1);
make_prefix();
k = 0;
for (i = 1; i <= m; ++ i)
{
while (k && a[k + 1] != b[i])
k = p[k];
if (a[k + 1] == b[i])
k ++;
if (k == n)
{
if (cont < 1000)
ans[++ cont] = i - n;
k = p[k];
}
}
g << cont << '\n';
for (i = 1; i <= cont; ++ i)
g << ans[i] << " ";
return 0;
}