Pagini recente » Cod sursa (job #2894074) | Cod sursa (job #2585747) | Cod sursa (job #846039) | Cod sursa (job #1477848) | Cod sursa (job #2740355)
#include <iostream>
#include <cstring>
#include <fstream>
int LPS[2000001];
void BuildLPS(char* pattern, int m) {
LPS[0] = 0;
int i = 1, j = 0;
while (i < m) {
if (pattern[i] == pattern[j])
LPS[i++] = ++j;
else {
if (j != 0)
j = LPS[j - 1];
else
LPS[i++] = 0;
}
}
}
int N = 0;
int poz[1000];
void KMP(char* text, char* pattern) {
int m = strlen(pattern);
BuildLPS(pattern, m);
int n = strlen(text);
int i = 0, j = 0;
while (i < n) {
if (text[i] == pattern[j]) {
++i;
++j;
if (j == m) {
if (N < 1000)
poz[N++] = i - j;
j = LPS[j - 1];
}
} else {
if (j != 0)
j = LPS[j - 1];
else
++i;
}
}
}
char A[2000001];
char B[2000001];
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
fin >> A >> B;
fin.close();
KMP(B, A);
fout << N << '\n';
for (int i = 0; i < N; ++i)
fout << poz[i] << ' ';
fout.close();
return 0;
}