Pagini recente » Cod sursa (job #828914) | Cod sursa (job #543071) | Cod sursa (job #1866734) | Cod sursa (job #104490) | Cod sursa (job #1503653)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
ifstream f ( "strmatch.in" );
const int MAX = 2000001;
string X , S;
int longps [ MAX ] , i , Xlen , Slen , Xi , Si , strmatch [ MAX ];
vector <int> matches;
void read()
{
getline ( f , X );
//set length
Xlen = X.size();
getline ( f , S );
//set length
Slen = S.size();
}
void prefix_suffix()
{
int pref = 0;
longps [ 0 ] = 0;
for ( i = 1 ; i < Xlen ; i ++ )
if ( X [ i ] == X [ pref ] )
{
longps [ i ] = longps [ i - 1 ] + 1;
pref ++;
}
else
{
longps [ i ] = 0;
pref = 0;
}
}
void KMP()
{
int Xi = 0;
for ( Si = 1 ; Si < Slen ; Si ++ )
if ( S [ Si ] == X [ Xi ] )
{
//set the new length
strmatch [ Si ] = strmatch [ Si - 1 ] + 1;
Xi ++;
if ( Xi == Xlen )
{
matches.push_back( Si - Xlen + 1 );
Xi = longps [ Xi - 1 ];
}
}
else
{
//set the new length
strmatch [ Si ] = 0;
Xi = 0;
if ( X [ Xi ] == S [ Si ] )
Si --;
}
}
void print()
{
int N = matches.size();
printf ( "%d\n" , N );
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();
}