Pagini recente » Cod sursa (job #2637787) | Cod sursa (job #2051486) | Cod sursa (job #3317505) | Cod sursa (job #1008454) | Cod sursa (job #1549232)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int ans,v[1010];
void prefix( char N[], int n, int pi[] )
{
int k = 0,i;
for( i = 2 ; i <= n ; i++ )
{
while( k > 0 && N[ k + 1 ] != N[ i ] )
k = pi[ k ];
if( N[ k + 1 ] == N[ i ] )
k = k + 1;
pi[ i ] = k;
}
}
void KMP( char N[], int n, char M[], int m, int pi[] )
{
int q = 0,i;
for( i = 1 ; i <= m ; i++ )
{
while( q > 0 && N[ q + 1 ] != M[ i ] )
q = pi[ q ];
if( N[ q + 1 ] == M[ i ] )
q = q + 1;
if( q == n - 1 && i <= 1000 )
v[ ++ans ] = i - n + 1;
}
}
char A[2000010],B[2000010];
int a,b,pi[2000010],i;
int main()
{
fin.get( A + 1 , 2000010 );
A[ 0 ] = ' ';
fin.get();
fin.get( B + 1 , 2000010 );
B[ 0 ] = ' ';
fin.get();
a = strlen( A );
b = strlen( B );
prefix( A , a , pi );
KMP( A , a , B , b , pi );
fout<<ans<<'\n';
for( i = 1 ; i <= ans ; i++ )
fout<<v[ i ]<< ' ';
return 0;
}