Pagini recente » Cod sursa (job #3174083) | Cod sursa (job #2003716) | Cod sursa (job #2227689) | Cod sursa (job #1928319) | Cod sursa (job #1998393)
#include<cstdio>
#include<cstring>
using namespace std;
#define Nmax 2000001
char A[Nmax], B[Nmax];
int pi[Nmax], pos[Nmax], n = 0;
void getPrefix()
{
int i = 0;
pi[0] = 0;
for( int j = 1; j<strlen(A)-1; j++ )
{
while( i && A[i] != A[j] )
i = pi[i-1];
if( A[i] == A[j] )
i++;
pi[j] = i;
}
// for( int j = 0; j < strlen(A); j++ )
// out<<pi[j]<<'\n';
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(A, sizeof(A), stdin);
fgets(B, sizeof(B), stdin);
getPrefix();
int i = 0, N = strlen(A) - 1, M = strlen(B) - 1;
for( int j = 0; j <= M; j++ )
{
int ct = 0;
while( i && A[i] != B[j])
{
ct++;
i = pi[i-1];
}
if( A[i] == B[j] )
i++;
if( i == N )
{
i = pi[N-1];
pos[++n] = j-N+1;
}
}
printf("%d\n", n);
for( int j = 1; j<=n && j<=1000; j++ )
printf("%d ", pos[j]);
printf("\n");
return 0;
}