Pagini recente » Borderou de evaluare (job #1036120) | Cod sursa (job #1192722) | Cod sursa (job #325317) | Cod sursa (job #1361307) | Cod sursa (job #216604)
Cod sursa(job #216604)
#include <cstdio>
#include <cstring>
#define min(a, b) ((a < b)? a : b)
#define MAX_N 2000005
#define MAX_S 1005
int N, M, pi[MAX_N];
char A[MAX_N], B[MAX_N];
int Nr, P[MAX_S];
void kmp(char *S)
{
int q = 0, i;
for(i = 2; i <= N; ++i)
{
while(q && S[q] != S[i-1])
q = pi[q];
if(S[q] == S[i-1])
++q;
pi[i] = q;
}
}
int main()
{
freopen("strmatch.in","rt",stdin);
freopen("strmatch.out","wt",stdout);
fgets(A, sizeof A, stdin);
fgets(B, sizeof B, stdin);
N = strlen(A) - 1;
M = strlen(B) - 1;
kmp(A);
for(int i = 0, q = 0; i < M; ++i)
{
while(q && A[q] != B[i])
q = pi[q];
if(A[q] == B[i])
++q;
if(q == N)
{
q = pi[N];
++Nr;
if(Nr < 1001)
P[Nr] = i - N + 1;
}
}
printf("%d\n",Nr);
for(int i = 1; i <= min(1000, Nr); ++i)
printf("%d ",P[i]);
}