Pagini recente » Cod sursa (job #13841) | Cod sursa (job #1185930) | Cod sursa (job #3290641) | Cod sursa (job #543714)
Cod sursa(job #543714)
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011
using namespace std;
int F[N_MAX];
int _countMatch;
vector< int > r;
string s, p;
inline void FunctionBuild(void)
{
int i, j, M=p.size()-1;
for( i=2; i <= M; ++i )
{
for( j=F[i-1]; j && p[j] != p[i-1]; j=F[j] );
if( p[j] == p[i-1] )
++j;
F[i]=j;
}
}
inline void KMP( void )
{
int i, j, N=s.size()-1, M=p.size()-1;
FunctionBuild();
for( i=j=0; i < N; )
{
if( s[i] == p[j] )
{
++i, ++j;
if( M == j )
{
++_countMatch;
if( _countMatch <= 1000 )
r.push_back(i-M);
}
}
else if( j )
j=F[j];
else ++i;
}
}
int main( void )
{
ifstream in( "strmatch.in" );
getline( in, p );
getline( in, s );
p.push_back(' ');
s.push_back(' ');
KMP();
ofstream out( "strmatch.out" );
out<<_countMatch<<'\n';
copy( r.begin(), r.end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}