Pagini recente » Cod sursa (job #2730986) | Cod sursa (job #459948) | Cod sursa (job #3286059) | Cod sursa (job #3281701) | Cod sursa (job #459808)
Cod sursa(job #459808)
#include <string>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define Nmax 2000111
/*
*
*/
using namespace std;
int Fprefix[Nmax];
vector< int > r;
string pattern, s;
void Fp( int M )
{
int i, j;
for( i=2; i <= M; ++i )
{
for( j=Fprefix[i-1]; j && pattern[i-1] != pattern[j] ; j=Fprefix[j] );
if( pattern[i-1] == pattern[j] )
++j;
Fprefix[i]=j;
}
}
void KMP( int N, int M )
{
int i, j;
Fp( M );
for( i=j=0; j < N; )
{
if( pattern[i] == s[j] )
{
++i, ++j;
if( M == i )
r.push_back( j-M );
}
else if( i )
i=Fprefix[i];
else ++j;
}
}
int main( void )
{
ifstream in( "strmatch.in" );
getline( in, pattern, '\n' );
getline( in, s );
KMP( s.size(), pattern.size() );
ofstream out( "strmatch.out" );
out<<r.size()<<'\n';
copy( r.begin(), r.begin() + ( 1000 <= r.size() ? 1000 : r.size() ), ostream_iterator< int >( out, " " ) );
return EXIT_SUCCESS;
}