Pagini recente » Cod sursa (job #2276922) | Cod sursa (job #3004624) | Cod sursa (job #2104665) | Cod sursa (job #2209691) | Cod sursa (job #2396542)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int LGMAX = 2000005;
string A, p;
int lps[LGMAX];
vector <int> pos;
void Read()
{
fin >> p >> A;
fin.close();
}
void Do()
{
if( p.size() > A.size() )
{
fout << 0 << '\n';
return;
}
int len = 0;
int sz = p.size();
for( int i = 1; i < sz; ++i )
{
if( p[len] == p[i] ) lps[i] = ++len;
else
if( len > 0 )
{
len = lps[len - 1];
--i;
}
}
int i, j;
i = j = 0;
sz = A.size();
while( i < sz )
{
if( p[j] == A[i] )
{
++i;
++j;
}
if( j == p.size() )
{
pos.push_back( i - j );
j = lps[j - 1];
}
else
if( i < sz && p[j] != A[i] )
{
if( j > 0 ) j = lps[j - 1];
else ++i;
}
}
sz = min( 1000, (int)pos.size() );
fout << pos.size() << '\n';
for( int i = 0; i < sz; ++i )
fout << pos[i] << ' ';
}
int main()
{
Read();
Do();
return 0;
}