Pagini recente » Cod sursa (job #3137342) | Cod sursa (job #2364848) | Monitorul de evaluare | Cod sursa (job #1329632) | Cod sursa (job #2366519)
#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[200010],ans[1010];
int main()
{
fin.get( a + 1 , 2000010 );
fin.get();
fin.get( b + 1 , 2000010 );
int n, m;
n = strlen( a + 1 );
m = strlen( b + 1 );
int poz = 0;
for( int i = 2 ; i <= n ; i++ )
{
while( poz != 0 && a[ i ] != a[ poz + 1 ] ) poz = pi[ poz ];
if( a[ i ] == a[ poz + 1 ] ) poz++;
pi[ i ] = poz;
}
poz = 0;
for( int i = 1 ; i <= m ; i++ )
{
while( poz != 0 && b[ i ] != a[ poz + 1 ] ) poz = pi[ poz ];
if( b[ i ] == a[ poz + 1 ] ) poz++;
if( poz == n )
{
ans[ 0 ]++;
if( ans[ 0 ] <= 1000 )
ans[ ans[ 0 ] ] = i - n;
poz = pi[ poz ];
}
}
fout << ans[ 0 ] << '\n';
for( int i = 1 ; i <= min( ans[ 0 ] , 1000 ) ; i++ )
fout << ans[ i ] << ' ';
fin.close();
fout.close();
return 0;
}