Pagini recente » Cod sursa (job #1970952) | Cod sursa (job #2153621) | Cod sursa (job #1511428) | Cod sursa (job #1120456) | Cod sursa (job #1549236)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000010],B[2000010];
int pi[2000010],ans[1010],i,j,a,b,sol,k;
int main()
{
fin.get( A + 1 , 2000010 ); fin.get();
fin.get( B + 1 , 2000010 );
A[ 0 ] = ' ';
B[ 0 ] = ' ';
a = strlen( A );
b = strlen( B );
for( i = 2 ; i <= a ; i++ )
{
while( k > 0 && A[ k + 1 ] != A[ i ] )
k = pi[ k ];
if( A[ k + 1 ] == A[ i ] )
k++;
pi[ i ] = k;
}
for( i = 1 ; i <= b ; i++ )
{
while( k > 0 && A[ k + 1 ] != B[ i ] )
k = pi[ k ];
if( A[ k + 1 ] == B[ i ] )
k++;
if( k == a - 1 )
{
++sol;
if( sol <= 1000 )
ans[ sol ] = i - a + 1;
}
}
fout<<sol<<'\n';
for( i = 1 ; i <= min( sol , 1000 ) ; i++ )
fout<<ans[ i ]<<' ';
return 0;
}