Pagini recente » Cod sursa (job #1371509) | Cod sursa (job #3225513) | Cod sursa (job #1446266) | Cod sursa (job #297621) | Cod sursa (job #494770)
Cod sursa(job #494770)
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define MAX_N 2000011
using namespace std;
/*
*
*/
int f[MAX_N];
vector< int > r;
string pattern, s;
inline int min( int x, int y )
{
if( x <= y )
return x;
return y;
}
inline void F( void )
{
int M=pattern.size(), i, j;
for( i=2; i <= M; ++i )
{
for( j=f[i-1]; j && pattern[i-1] != pattern[j]; j=f[j] );
if( pattern[i-1] == pattern[j] )
++j;
f[i]=j;
}
}
inline void KMP( void )
{
int i, j, N=s.size(), M=pattern.size();
F();
for( i=j=0; i < N; )
{
if( pattern[j] == s[i] )
{
++i, ++j;
if( M == j )
r.push_back(i-M);
}
else if( j )
j=f[j];
else ++i;
}
}
int main( void )
{
ifstream in( "strmatch.in" );
in>>pattern>>s;
KMP();
ofstream out( "strmatch.out" );
out<<r.size()<<'\n';
copy( r.begin(), r.begin()+min( 1000, r.size() ), ostream_iterator<int>( out, " " ) );
out<<'\n';
return EXIT_SUCCESS;
}