Pagini recente » Cod sursa (job #884991) | Cod sursa (job #3244293) | Cod sursa (job #622920) | Cod sursa (job #268922) | Cod sursa (job #614383)
Cod sursa(job #614383)
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
int match;
string s, pattern;
vector< int > v, failFunction;
void BuildF()
{
int M=pattern.size(), i, j;
failFunction.push_back( 0 );
failFunction.push_back( 0 );
for( i=2; i <= M; ++i )
{
for( j=failFunction[i-1]; j && pattern[i-1] != pattern[j]; j=failFunction[j] );
if( pattern[i-1] == pattern[j] )
++j;
failFunction.push_back(j);
}
}
void KMP()
{
BuildF();
int i, j, N=s.size(), M=pattern.size();
s.push_back(' ');
pattern.push_back(' ');
for( i=j=0; i < N; )
{
if( s[i] == pattern[j] )
{
++i, ++j;
if( M == j )
{
++match;
if( match <= 1000 )
v.push_back( i-M );
}
}
else if( j )
j=failFunction[j];
else ++i;
}
s.erase( s.end()-1 );
pattern.erase( pattern.end()-1 );
}
int main( void )
{
ifstream in( "strmatch.in" );
getline( in, pattern );
getline( in, s );
KMP();
ofstream out( "strmatch.out" );
out<<match<<'\n';
copy( v.begin(), v.end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}