Pagini recente » Cod sursa (job #856647) | Cod sursa (job #61165) | Cod sursa (job #2927011) | Cod sursa (job #120186) | Cod sursa (job #1577850)
#include<cstdio>
#include<cstring>
#include<vector>
#define DIM 2000010
#define Minim(x, y) (x <= y ? x : y)
using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
int N, M;
int k, i, p[DIM];
int v[DIM];
char S1[DIM], S2[DIM];
vector <int> sol;
int main()
{
gets(S1 + 1); M = strlen(S1 + 1);
gets(S2 + 1); N = strlen(S2 + 1);
k=0; p[1]=0;
for (i = 2; i <= M; i++)
{
while (k > 0 && S1[i] != S1[k + 1])
k = p[k];
if (S1[i] == S1[k + 1])
++k;
p[i] = k;
}
/*for (int i = 1; i <= M; i++)
printf("%d ", p[i]);*/
k = 0;
for (int i = 1; i <= N; i++)
{
while (k && S2[i] != S1[k + 1])
k = p[k];
if (S2[i] == S1[k + 1])
k ++;
if (k == M)
{
sol.push_back(i - M);
k = p[k];
}
}
printf("%d\n", sol.size());
for (int i = 0; i < Minim(sol.size(), 1000u); i++)
printf("%d ", sol[i]);
}