Pagini recente » Cod sursa (job #696005) | Cod sursa (job #1971869) | Cod sursa (job #2066919) | Cod sursa (job #1489186) | Cod sursa (job #2279767)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define val 2000005
char P[ val ], T[ val ];
int n, m, i, j, D[ val ], rez, inc, vT[ val ], sol;
int main()
{
fin.get( P, val );
fin.get();
fin.get( T, val );
n = strlen( P );
m = strlen( T );
i = 0;
for ( j = 1; j <= n - 1; j++ )
{
if ( P[ j ] == P[ i ] )
{
D[ j ] = D[ j - 1 ] + 1;
i++;
}
else
{
if ( i > 0 )
{
j--;
}
i = 0;
}
}
j = 0;
for ( i = 0; i <= m - 1; i++ )
{
if ( T[ i ] == P[ j ] )
{
if ( j == n - 1 )
{
rez++;
vT[ i - n + 1 ] = 1;
}
j++;
}
else
{
if ( j > 0 )
{
j = D[ j - 1 ];
i--;
}
}
}
fout<<rez << '\n';
rez = min ( rez, 1000 );
for ( i = 0; i <= m - 1 && sol < rez; i++ )
{
if ( vT[ i ] )
{
fout<< i << ' ';
sol++;
}
}
fin.close();
fout.close();
return 0;
}