Pagini recente » Cod sursa (job #1819334) | Cod sursa (job #1964833) | Cod sursa (job #3247171) | Cod sursa (job #1927775) | Cod sursa (job #1920998)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e6 + 10;
string a, b;
int phi[nmax];
int cnt;
vector < int > ans;
void input() {
cin >> a >> b;
a = ' ' + a; b = ' ' + b;
}
void compute_phi(string str) {
int k = 0;
for (int i = 2; i < (int)str.size(); ++i) {
while (k && str[k+1] != str[i])
k = phi[k];
if (str[k+1] == str[i]) k++;
phi[i] = k;
}
}
void get_ans(string a, string str) {
int k = 0;
for (int i = 1; i < (int)str.size(); ++i) {
while (k && a[k+1] != str[i])
k = phi[k];
if (a[k+1] == str[i]) k++;
if (k + 1 == (int)a.size()) {
cnt++;
if (cnt <= 1000) ans.push_back(i - (int)a.size() + 1);
}
}
}
void output() {
printf("%d\n", cnt);
for (auto &it: ans) printf("%d ", it);
}
int main() {
ios::sync_with_stdio(false);
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
input();
compute_phi(a);
get_ans(a, b);
output();
return 0;
}