Pagini recente » Cod sursa (job #2761421) | Cod sursa (job #889983) | Cod sursa (job #2802854) | Cod sursa (job #1674079) | Cod sursa (job #1630890)
#include <fstream>
#include <string>
using namespace std;
int Z[4000010],i,j,n,m,l,r,k,ans[1010];
string a,b;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void expand()
{
while( a[ r + 1 ] == a[ r - l + 1 ] && r <= a.size() )
r++;
}
int main()
{
fin>>a;
k = a.size();
Z[ 0 ] = k;
a += "$";
fin>>b;
a += b;
for( i = 1 ; i < a.size() ; i++ )
{
Z[ i ] = 0;
if( l <= i && i <= r )
{
if( Z[ i - l ] >= r - i + 1 )
{
l = i;
expand();
Z[ i ] = r - l + 1;
}
else
Z[ i ] = Z[ i - l ];
}
else if( a[ i ] == a[ 0 ] )
{
l = r = i;
expand();
Z[ i ] = r - l + 1;
}
if( Z[ i ] == k )
{
++ans[0];
if( ans[ 0 ] <= 1000 )
ans[ ans[ 0 ] ] = i;
}
}
fout<<ans[ 0 ]<<'\n';
for( i = 1 ; i <= min( ans[ 0 ] , 1000 ) ; i++ )
fout<<ans[ i ]-k-1<<' ';
return 0;
}