Pagini recente » Cod sursa (job #2809497) | Cod sursa (job #1324405) | Cod sursa (job #2046131) | Cod sursa (job #2514602) | Cod sursa (job #1552512)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string a;
cin >> a;
string b;
cin >> b;
vector<int> c(a.size()+1);
int l = 0;
int r = 0;
for (int i = 1; i <= a.size(); i++) {
if (l+c[i-l] < r) {
c[i] = l+c[i-l];
} else {
l = i;
r = max(r, i);
while (r < a.size() && a[r-i] == a[r]) r++;
c[i] = r;
}
}
vector<int> ans;
l = 0;
r = 0;
for (int i = 0; i <= b.size(); i++) {
if (l+c[i-l] >= r) {
l = i;
r = max(r, i);
while (r < b.size() && a[r-i] == b[r]) r++;
if (r-l == a.size()) {
ans.push_back(l);
}
}
}
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf("%d%c", ans[i], " \n"[i == ans.size()-1]);
}
}