Pagini recente » Cod sursa (job #2701095) | Cod sursa (job #1772761) | Cod sursa (job #424099) | Cod sursa (job #1758470) | Cod sursa (job #1148232)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_LEN = 2000002;
int N, M, ans = 0;
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(ans < 1000)
sol.push_back(i - N);
++ans;
}
}
}
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 << ans << "\n";
for(size_t i = 0; i < sol.size(); ++i)
g << sol[i] << " ";
g << "\n";
f.close();
g.close();
return 0;
}