Pagini recente » Cod sursa (job #106578) | Cod sursa (job #3153387) | Cod sursa (job #3133491) | Cod sursa (job #372569) | Cod sursa (job #2941546)
#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;
vector<int> ans;
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.size() < 1000)
ans.push_back(i - j);
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 << ans.size() << '\n';
for (int i = 0; i < ans.size(); i++)
fout << ans[i] << ' ';
fin.close();
fout.close();
return 0;
}