Pagini recente » Cod sursa (job #1311614) | Cod sursa (job #66972) | Cod sursa (job #1370748) | Cod sursa (job #1113153) | Cod sursa (job #415806)
Cod sursa(job #415806)
# include <algorithm>
# include <fstream>
# include <string>
# include <vector>
using namespace std;
# define Lim 1000
# define Max_N 2000005
const char Input[] = "strmatch.in";
const char Output[] = "strmatch.out";
int N, M, Nr_sol;
int pi[ Max_N ];
string A, B;
vector <int> sol;
void calc_pi() {
int i, k;
k = 0;
pi[ 1 ] = 0;
for( i = 2; i <= N; ++i ) {
while( k > 0 && A[ k+1 ] != A[ i ] )
k = pi[ k ];
if( A[ k+1 ] == A[ i ] )
++k;
pi[ i ] = k;
}
}
int main() {
ifstream fin( Input );
ofstream fout( Output );
int i, k;
vector <int> :: iterator it;
fin >> A >> B;
N = A.length();
M = B.length();
A.insert( 0, "X" );
B.insert( 0, "X" );
k = 0;
calc_pi();
for( i = 1; i <= M && Nr_sol < Lim; ++i ) {
while( k > 0 && A[ k+1 ] != B[ i ] )
k = pi[ k ];
if( A[ k+1 ] == B[ i ] )
++k;
if( k == N ) {
k = pi[ k ];
++Nr_sol;
sol.push_back( i-N );
}
}
fout << Nr_sol << "\n";
for( it = sol.begin(); it != sol.end(); ++it )
fout << *it << " ";
fin.close();
fout.close();
return 0;
}