Pagini recente » Cod sursa (job #1958257) | Cod sursa (job #1615121) | Cod sursa (job #1423070) | Cod sursa (job #1219539) | Cod sursa (job #1632386)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[4000010];
int Z[4000010],i,j,n,m,ans,l,r,sol[1010],k;
void expand()
{
while( N[ r + 1 ] == N[ r - l + 1 ] && r < n )
r++;
}
int main()
{
fin.get( N , 2000010 ); fin.get();
k = strlen( N );
Z[ 0 ] = k;
N[ k ] = '$';
fin.get( N + k + 1 , 2000010 );
n = strlen( N );
for( i = 1 ; i < n ; i++ )
{
Z[ i ] = 0;
if( l <= i && i <= r )
{
if( Z[ i - l ] > r - i )
{
l = i;
expand();
Z[ i ] = r - l + 1;
}
else
Z[ i ] = Z[ i - l ];
}
else if( N[ i ] == N[ 0 ] )
{
l = r = i;
expand();
Z[ i ] = r - l + 1;
}
if( Z[ i ] == k )
{
++ans;
if( ans <= 1000 )
sol[ ans ] = i - k - 1;
}
}
fout<<ans<<'\n';
for( i = 1 ; i <= min( 1000 , ans ) ; i++ )
fout<<sol[ i ]<<' ';
return 0;
}