Pagini recente » Cod sursa (job #3355012) | Cod sursa (job #978388) | Cod sursa (job #987098) | Cod sursa (job #3328550) | Cod sursa (job #613185)
Cod sursa(job #613185)
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
string s, pattern;
vector< int > failF, ans;
int sSize, patternSize, ansSize;
void FailureFunction()
{
int i, j;
failF.push_back(0);
failF.push_back(0);
for( i=2; i <= patternSize; ++i )
{
for( j=failF[i-1]; j && pattern[i-1] != pattern[j]; j=failF[j] );
if( pattern[i-1] == pattern[j] )
++j;
failF.push_back(j);
}
}
void KMP()
{
int i, j;
FailureFunction();
pattern.push_back(' ');
s.push_back(' ');
for( i=j=0; i < sSize; )
{
if( s[i] == pattern[j] )
{
++i, ++j;
if( patternSize == j )
{
++ansSize;
if( 1000 >= ansSize )
ans.push_back( i-patternSize );
}
}
else if( j )
j=failF[j];
else ++i;
}
pattern.erase( pattern.end()-1 );
s.erase( s.end()-1 );
}
int main( void )
{
ifstream in( "strmatch.in" );
getline( in, pattern );
getline( in, s );
patternSize=pattern.size();
sSize=s.size();
KMP();
ofstream out( "strmatch.out" );
out<<ansSize<<'\n';
copy( ans.begin(), ans.end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}