Pagini recente » Cod sursa (job #2852945) | Cod sursa (job #1503743) | Cod sursa (job #453091) | Cod sursa (job #993150) | Cod sursa (job #1503732)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
ifstream f ( "strmatch.in" );
const int MAX = 2000005;
string X , S;
int longps [ MAX ] , i , Xlen , Slen , N , pref;
vector <int> matches;
void read()
{
getline ( f , X );
//set length
X = ' ' + X;
Xlen = X.size();
getline ( f , S );
//set length
S = ' ' + S;
Slen = S.size();
}
void prefix_suffix()
{
pref = 0;
longps [ 0 ] = -1;
longps [ 1 ] = 0;
for ( i = 2 ; i < Xlen ; i++ )
{
pref = longps [ i - 1 ];
while ( pref >= 0 && X [ pref + 1 ] != X [ i ] )
pref = longps [ pref ];
longps [ i ] = pref + 1;
}
}
void KMP()
{
pref = 0;
for ( i = 1 ; i < Slen ; i++ )
{
while ( pref > 0 && S [ i ] != X [ pref + 1 ] )
pref = longps [ pref ];
if ( S [ i ] == X [ pref + 1 ] )
pref ++;
if ( pref == Xlen - 1 )
{
pref = longps [ pref ];
N ++;
if ( N <= 1000 )
matches.push_back ( i - Xlen + 1 );
}
}
}
void print()
{
printf ( "%d\n" , N );
N = min ( N , 1000 );
for ( i = 0 ; i < N ; i ++ )
printf ( "%d " , matches [ i ] );
printf ( "\n" );
}
int main()
{
freopen ( "strmatch.out" , "w" , stdout );
read();
//find the longest prefix that's also a suffix in X
prefix_suffix();
//search for string matches by moving X according to longps
KMP();
print();
}