Pagini recente » Cod sursa (job #1713029) | Cod sursa (job #3221336) | Cod sursa (job #1821953) | Cod sursa (job #63871) | Cod sursa (job #1411042)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 2000010
using namespace std;
int n , m , i , j , pi[Nmax] , sol[1010];
char A[Nmax] , B[Nmax];
void make_prefix()
{
for (pi[1] = j = 0 , i = 2; i <= n; ++i)
{
while (j && A[j] != A[pi[j-1]+1]) j = pi[j];
if (A[j+1] == A[i]) j++;
pi[i] = j;
}
}
void make_kmp()
{
for (j = 0 , i = 1; i <= m; ++i)
{
while (j && B[i] != A[j+1]) j = pi[j];
if (A[j+1] == B[i]) j++;
if (j == n && sol[0] < 1000) sol[++sol[0]] = i - n;
else if (j == n) sol[0]++;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A + 1); n = strlen(A+1);
gets(B + 1); m = strlen(B+1);
make_prefix();
make_kmp();
for (printf("%d\n", sol[0]) , i = 1; i <= min(sol[0],1000); ++i)
printf("%d ", sol[i]);
return 0;
}