Pagini recente » Cod sursa (job #2982214) | Cod sursa (job #9989) | Cod sursa (job #650981) | Cod sursa (job #35931) | Cod sursa (job #1391874)
#include<stdio.h>
#include<string.h>
#define LMAX 2000001
char N[LMAX] , M[LMAX];
int pi[LMAX] , n , m , sol[1001];
void prefix();
void solve();
int main()
{
freopen("strmatch.in" , "r" , stdin );
freopen("strmatch.out" , "w" , stdout );
scanf("%s%s" , N+1 , M+1);
n = strlen(N+1);
m = strlen(M+1);
prefix();
solve();
printf("%d\n" , sol[0]);
for(int i = 1 ; i <= sol[0] ; ++i )
printf("%d " , sol[i]-1 );
return 0;
}
void prefix()
{
int k = 0;
for(int i = 2 ; i <= n ; ++i ){
while(k && N[i] != N[k+1])
k = pi[k];
if(N[i] == N[k+1])
k++;
pi[i] = k;
}
}
void solve()
{
int k = 0;
for(int i = 1 ; i <= m && sol[0] < 1000 ; ++i ){
while(k && M[i] != N[k+1])
k = pi[k];
if(M[i] == N[k+1])
k++;
if(k == n)
sol[++sol[0]] = i-n+1;
}
}