Pagini recente » Cod sursa (job #2516421) | Cod sursa (job #1266102) | Cod sursa (job #2561061) | Istoria paginii runda/simulare_de_oni_4 | Cod sursa (job #1923375)
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
char a[2000010],b[2000010];
int pi[2000010],i,j,n,m,sol[1010],ans,k;
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;
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;
if( k == n )
{
++ans;
if( ans <= 1000 )
sol[ ans ] = i - n;
k = pi[ k ];
}
}
fout<<ans<<'\n';
for( i = 1 ; i <= min( ans , 1000 ) ; i++ )
fout<<sol[ i ]<<' ';
return 0;
}