Pagini recente » Cod sursa (job #1202102) | Cod sursa (job #1437931) | Cod sursa (job #1480640) | Cod sursa (job #932858) | Cod sursa (job #2366524)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
char a[2000010],b[2000010];
int pi[2000010],i,j,n,m,k,v[1010],ans;
int main()
{
fin.get( a + 1 , 2000010 );
fin.get();
fin.get( b + 1 , 2000010 );
n = strlen( a + 1 );
m = strlen( b + 1 );
k = 0;
for( i = 2 ; i <= n ; 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 <= m ; i++ )
{
while( k > 0 && a[ k + 1 ] != b[ i ] )
k = pi[ k ];
if( a[ k + 1 ] == b[ i ] )
k = k + 1;
if( k == n )
{
++ans;
if( ans <= 1000 )
v[ ans ] = i - n;
k = pi[ k ];
}
}
fout<<ans<<'\n';
for( i = 1 ; i <= min( ans , 1000 ) ; i++ )
fout<<v[ i ]<<' ';
return 0;
}