Pagini recente » Istoria paginii runda/cdib_8910 | Cod sursa (job #2617607) | Cod sursa (job #1851814) | Cod sursa (job #1276891) | Cod sursa (job #3120553)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void computeLPS(string A, int M, vector<int>& lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (A[i] == A[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
void KMP(string A, string B) {
int M = A.length();
int N = B.length();
vector<int> lps(M);
computeLPS(A, M, lps);
int i = 0, j = 0, count = 0;
vector<int> positions;
while (i < N) {
if (A[j] == B[i]) {
i++;
j++;
}
if (j == M) {
count++;
positions.push_back(i - j);
j = lps[j - 1];
}
else if (i < N && A[j] != B[i]) {
if (j != 0) {
j = lps[j - 1];
}
else {
i++;
}
}
}
fout << count << endl;
for (int k = 0; k < min(count, 1000); k++) {
fout << positions[k] << " ";
}
}
int main() {
string A, B;
fin >> A >> B;
fin.close();
KMP(A, B);
fout.close();
return 0;
}