Pagini recente » Cod sursa (job #2104625) | Cod sursa (job #2537814) | Cod sursa (job #118836) | Borderou de evaluare (job #1036688) | Cod sursa (job #2941549)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
constexpr size_t LIM = 2e6 + 5;
char pat[LIM], txt[LIM];
int lps[LIM], N, M, cnt, ans[1000];
static inline void compute_lps() {
lps[0] = 0;
int len = 0, i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0)
len = lps[len - 1];
else {
lps[i] = 0;
i++;
}
}
}
}
static inline void kmp() {
int i = 0, j = 0;
while ((N - i) >= (M - j)) {
if (pat[j] == txt[i])
i++, j++;
if (j == M) {
if (ans[0] < 1000)
ans[++ans[0]] = i - j;
cnt++;
j = lps[j - 1];
} else if(i < N && pat[j] != txt[i]) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}
int main(void) {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> pat >> txt;
N = strlen(txt);
M = strlen(pat);
compute_lps();
kmp();
fout << cnt << '\n';
for (int i = 1; i <= ans[0]; i++)
fout << ans[i] << ' ';
fin.close();
fout.close();
return 0;
}