Pagini recente » Cod sursa (job #2156382) | Cod sursa (job #2969922) | Cod sursa (job #579589) | Cod sursa (job #2372498) | Cod sursa (job #559354)
Cod sursa(job #559354)
#include <algorithm>
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;
const char Input[] = "strmatch.in";
const char Output[] = "strmatch.out";
const int Dim = 2000001;
char A[Dim], B[Dim];
int N, M, XXX, Pi[Dim];
vector <int> sol;
void GetPi() {
int i, k;
k = 0;
Pi[1] = 0;
for( i = 2; i <= N; ++i ) {
while( k > 0 && A[k] != A[i - 1] )
k = Pi[k];
if( A[k] == A[i - 1] )
++k;
Pi[i] = k;
}
}
void KMP() {
int i, q;
q = 0;
for( i = 1; i <= M; ++i ) {
while( q > 0 && A[q] != B[i - 1] )
q = Pi[q];
if( A[q] == B[i - 1] )
++q;
if( q == N )
if( ++XXX <= 1000 )
sol.push_back( i - N );
}
}
int main() {
ifstream fin( Input );
ofstream fout( Output );
vector <int> :: iterator it;
fin.getline( A, Dim );
fin.getline( B, Dim );
N = strlen( A );
M = strlen( B );
GetPi();
KMP();
fout << XXX << "\n";
for( it = sol.begin(); it != sol.end(); ++it )
fout << *it << " ";
fin.close();
fout.close();
return 0;
}