Pagini recente » Cod sursa (job #60151) | Cod sursa (job #57617) | Cod sursa (job #278459) | Cod sursa (job #2702878) | Cod sursa (job #1148231)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_LEN = 2000002;
int N, M;
int Pi[MAX_LEN];
vector < int > sol;
char A[MAX_LEN], B[MAX_LEN];
void prefix() {
for(int i = 2, p = 0; i <= N; ++i) {
while(p > 0 && A[p + 1] != A[i])
p = Pi[p];
if(A[p + 1] == A[i])
++p;
Pi[i] = p;
}
}
void KMP() {
for(int i = 1, p = 0; i <= M; ++i) {
while(p > 0 && A[p + 1] != B[i])
p = Pi[p];
if(A[p + 1] == B[i])
++p;
if(p == N) {
if(sol.size() < 1000)
sol.push_back(i - N);
}
}
}
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
A[0] = B[0] = ' ';
f >> (A + 1);
f >> (B + 1);
N = strlen(A) - 1, M = strlen(B) - 1;
prefix();
KMP();
g << sol.size() << "\n";
for(size_t i = 0; i < sol.size(); ++i)
g << sol[i] << " ";
g << "\n";
f.close();
g.close();
return 0;
}