Pagini recente » Cod sursa (job #1821399) | Cod sursa (job #133278) | Cod sursa (job #2353763) | Cod sursa (job #2719325) | Cod sursa (job #522178)
Cod sursa(job #522178)
/*
* File: main.cpp
* Author: salexandru
*
* Created on January 14, 2011, 2:32 PM
*/
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011
using namespace std;
/*
*
*/
string s, p;
int F[N_MAX];
vector< int > v;
inline void EFunction(void)
{
int i, j, M=p.size();
for( i=2; i <= M; ++i )
{
for( j=F[i-1]; j && p[i-1] != p[j]; j=F[j] );
if( p[i-1] == p[j] )
++j;
F[i]=j;
}
}
inline void KMP(void)
{
EFunction();
int i, j, N=s.size(), M=p.size();
p.push_back(' ');
for( i=j=0; i < N; )
{
if( s[i] == p[j] )
{
++i, ++j;
if( j == M )
v.push_back(i-M);
}
else if( j )
j=F[j];
else ++i;
}
}
inline int min( int x, int y )
{
return ( x >= y ? y : x );
}
int main(int argc, char** argv)
{
ifstream in( "strmatch.in" );
getline( in, p );
getline( in, s );
KMP();
ofstream out( "strmatch.out" );
out<<v.size()<<'\n';
copy( v.begin(), v.begin()+min( 1000, v.size() ), ostream_iterator<int>( out, " ") );
return 0;
}