Pagini recente » Cod sursa (job #1953001) | Diferente pentru problema/mesaje intre reviziile 10 si 11 | Monitorul de evaluare | Cod sursa (job #1878921) | Cod sursa (job #1549235)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000010],B[2000010];
int pi[2000010],i,j,a,b,ans[1010],k;
int main()
{
fin.get( A + 1 , 2000010 ); fin.get();
fin.get( B + 1 , 2000010 ); fin.get();
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 = k + 1;
pi[ i ] = k;
}
k = 0;
for( i = 1 ; i <= b ; i++ )
{
while( k > 0 && A[ k + 1 ] != B[ i ] )
k = pi[ k ];
if( A[ k + 1 ] == B[ i ] )
k = k + 1;
if( k == a - 1 )
{
if( ans[ 0 ] <= 1000 )
ans[ ++ans[ 0 ] ] = i - a + 1;
else
ans[ 0 ]++;
}
}
fout<<ans[ 0 ]<<'\n';
for( i = 1 ; i <= min( ans[ 0 ] , 1000 ) ; i++ )
fout<<ans[ i ]<<' ';
return 0;
}