Pagini recente » Cod sursa (job #928808) | Cod sursa (job #1016429) | Cod sursa (job #3152536) | Cod sursa (job #1514675) | Cod sursa (job #1420722)
// KMP - O(N+M)
#include <fstream>
#include <cstring>
#include <vector>
#define Nmax 2000099
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N, M, pi[Nmax];
char A[Nmax], B[Nmax];
vector<int> sol;
void KMP(const char A[Nmax], const char B[Nmax], vector<int> &sol) {
int q, N, M;
N = strlen(A+1), M = strlen(B+1);
for (int i = 0; i <= N; i++) {
pi[i] = 0;
}
q = 0;
pi[1] = 0;
for(int i = 2; i <= N; ++i) {
while(q && A[q+1] != A[i]) q = pi[q];
if(A[q+1] == A[i]) ++q;
pi[i] = q;
}
q = 0;
for(int i = 1; i <= M; ++i) {
while(q && A[q+1] != B[i]) q = pi[q];
if(A[q+1] == B[i]) ++q;
if(q == N) {
sol.push_back(i-N+1);
//q = pi[N];
if (sol.size() == 1000) return;
}
}
}
int main() {
f >> (A+1) >> (B+1) ;
N = strlen(A+1);
M = strlen(B+1);
KMP(A, B, sol);
g << sol.size() << '\n';
for(int i = 0; i < min((int)sol.size(), 1000); ++i) g << sol[i] - 1 << ' ';
g << '\n';
f.close();g.close();
return 0;
}