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