Pagini recente » Cod sursa (job #2968785) | Cod sursa (job #1458615) | Cod sursa (job #2172717) | Cod sursa (job #1047322) | Cod sursa (job #1891947)
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_STR 2000005
using namespace std;
auto fin = fopen("strmatch.in", "r");
auto fout = fopen("strmatch.out", "w");
char a[MAX_STR], b[MAX_STR];
unsigned int lena, lenb;
vector<int> matches;
void input() {
fscanf(fin, "%s", a);
fscanf(fin, "%s", b);
lena = strlen(a);
lenb = strlen(b);
}
void output() {
fprintf(fout, "%d\n", matches.size());
for (auto match: matches)
fprintf(fout, "%d ", match);
}
vector<int> getPrefix(const char* s, unsigned int lens) {
vector<int> res;
res.reserve(lens + 1);
res.push_back(-1);
auto k = -1;
for (auto i = 1u; i <= lens; ++i) {
while (k != -1 && s[k] != s[i - 1])
k = res[k];
k += 1;
res.push_back(k);
}
return res;
}
void solve() {
auto pref = getPrefix(a, lena);
auto k = 0, i = 0;
while (i <= lenb - lena) {
if (k == lena) {
matches.push_back(i);
i += k - pref[k];
k = max(pref[k], 0);
}
if (a[k] == b[i + k])
++k;
else {
i += k - pref[k];
k = max(pref[k], 0);
}
}
}
int main() {
input();
solve();
output();
return 0;
}