Pagini recente » Cod sursa (job #1689005) | Cod sursa (job #2904156) | Cod sursa (job #1974559) | Cod sursa (job #104874) | Cod sursa (job #2740367)
#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 print = 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 (print < 1000)
poz[print++] = i - j;
N++;
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.getline(A, 2000001);
fin.getline(B, 2000001);
fin.close();
KMP(B, A);
fout << N << '\n';
for (int i = 0; i < print; ++i)
fout << poz[i] << ' ';
fout << '\n';
fout.close();
return 0;
}