Pagini recente » Cod sursa (job #1710569) | Cod sursa (job #682509) | Cod sursa (job #2380862) | Cod sursa (job #1940861) | Cod sursa (job #1414932)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;
#define maxn 2000005
int na, nb ;
char A[maxn], B[maxn] ;
int pi[maxn], sol[1005] ;
void prefix()
{
pi[1] = 0 ;
int k = 0 ;
for(int i = 2; i <= na; ++i)
{
while( k > 0 && A[k + 1] != A[i] )
k = pi[k] ;
if( A[k + 1] == A[i] )
++k ;
pi[i] = k ;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", A + 1);
na = strlen(A + 1) ;
scanf("%s\n", B + 1);
nb = strlen(B + 1) ;
prefix() ;
int q = 0 ;
for(int i = 1; i <= nb; ++i)
{
while( q > 0 && A[q + 1] != B[i] )
q = pi[q] ;
if( A[q + 1] == B[i] )
++q ;
if( q == na )
{
++sol[0] ;
if( sol[0] < 1001 )
sol[ sol[0] ] = i - na ;
}
}
printf("%d\n", sol[0]);
for(int i = 1; i <= min( sol[0], 1000 ); ++i)
printf("%d ", sol[i]);
return 0 ;
}