Pagini recente » Cod sursa (job #131479) | Cod sursa (job #163054) | Cod sursa (job #903944) | Cod sursa (job #3261106) | Cod sursa (job #701514)
Cod sursa(job #701514)
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011
using namespace std;
int countMatch;
string pattern, s;
int lengthPS[N_MAX];
vector< int > match;
void failureFunction( int M )
{
int i, j=0;
for( i=2; i <= M; ++i )
{
for( ; pattern[i-1] != pattern[j] && j; j=lengthPS[j] );
if( pattern[i-1] == pattern[j] )
++j;
lengthPS[i]=j;
}
}
void KMP( int N, int M )
{
int i, j;
pattern.push_back( ' ' );
failureFunction( M );
for( i=j=0; i < N; )
{
if( pattern[j] == s[i] )
{
++i, ++j;
if( M == j )
{
++countMatch;
if( countMatch <= 1000 )
match.push_back( i-M );
}
}
else if( j )
j=lengthPS[j];
else ++i;
}
pattern.erase( pattern.end()-1 );
}
int main()
{
ifstream in( "strmatch.in" );
ofstream out( "strmatch.out" );
getline( in, pattern );
getline( in, s );
KMP( s.size(), pattern.size() );
out<<countMatch<<'\n';
copy( match.begin(), match.end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}