Pagini recente » Cod sursa (job #2164873) | Cod sursa (job #2506897) | Cod sursa (job #590387) | Cod sursa (job #2611477) | Cod sursa (job #1161809)
#include <fstream>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
const int MAX = 2000050;
char A[MAX], B[MAX];
int ans, pfix[MAX];
vector<int> V;
void citire() {
ifstream in("strmatch.in");
in.getline(A + 1, MAX);
in.getline(B + 1, MAX);
in.close();
}
void kmp() {
int N = strlen(A + 1), M = strlen(B + 1);
pfix[1] = 0;
for(int i = 2, poz = 0; i <= N; i++) {
while(poz && A[poz + 1] != A[i])
poz = pfix[poz];
if(A[poz + 1] == A[i]) poz++;
pfix[i] = poz;
}
for(int i = 1, poz = 0; i <= M; i++) {
while(poz && A[poz + 1] != B[i])
poz = pfix[poz];
if(A[poz + 1] == B[i])
poz++;
if(poz == N) {
ans++;
if(V.size() < 1000)
V.push_back(i - N);
poz = pfix[poz];
}
}
}
void afisare() {
ofstream out("strmatch.out");
out << ans << "\n";
for(size_t i = 0; i < V.size(); i++)
out << V[i] << " ";
out << "\n";
out.close();
}
int main() {
citire();
kmp();
afisare();
}