Pagini recente » Cod sursa (job #99639) | Cod sursa (job #2650657) | Cod sursa (job #1443108) | Cod sursa (job #251299) | Cod sursa (job #1376693)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#define NMAX 2000005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in ( "strmatch.in" );
ofstream out ( "strmatch.out" );
char Line1[NMAX] ,Line2[NMAX] ;
int pref[NMAX] , N , M , Answer ;
vector < int > Sol;
void CreatePref ( void ){
int i , j , q ;
for ( i = 2 , q = 0 ; i <= N ; ++i ){
while ( Line1[i] != Line1[q+1] and q )
q = pref[q];
if( Line1[i] == Line1[q+1])
++q;
pref[i] = q;
}
}
void DoKMP ( void ){
int i , j , q;
CreatePref();
for ( i = 1 , q = 0; i <= M ; ++i ){
while( Line2[i] != Line1[q+1] and q )
q = pref[q];
if ( Line2[i] == Line1[q+1] )
++q;
if ( q == N){
++Answer;
q = pref[q];
Sol.push_back ( i-N );
}
}
}
int main ( void ) {
int i , j ;
Line1[0] = Line2[0] = ' ';
in >> ( Line1+ 1 ) , N = strlen(Line1) , --N;
in >> ( Line2 + 1 ) , M = strlen(Line2) , --M;
DoKMP();
out << Answer << "\n";
for ( vector < int > ::iterator it = Sol.begin() ; it != Sol.end() ; ++it )
out << *it << " ";
in.close();
out.close();
return 0 ;
}