Pagini recente » Cod sursa (job #2653502) | Cod sursa (job #1165318) | Cod sursa (job #258410) | Cod sursa (job #465753) | Cod sursa (job #2187383)
#include <bits/stdc++.h>
using namespace std;
int cnt;
string a, b;
vector < int > phi, ans;
void compute_phi(string s) {
phi = vector < int > ((int)s.size(), 0);
int k = 0;
for (int i = 2; i < (int)s.size(); ++i) {
while (k && s[k+1] != s[i])
k = phi[k];
if (s[k+1] == s[i]) k++;
phi[i] = k;
}
}
void compute_ans(string S, string s) {
int k = 0;
for (int i = 1; i < (int)S.size(); ++i) {
while (k && s[k+1] != S[i])
k = phi[k];
if (s[k+1] == S[i]) k++;
if (k == (int)s.size() - 1) {
cnt++;
if (cnt <= 1000)
ans.push_back(i - k);
}
}
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
ios_base :: sync_with_stdio(false);
cin >> a >> b;
a = ' ' + a; b = ' ' + b;
compute_phi(a);
compute_ans(b, a);
cout << cnt << '\n';
for (auto &it: ans)
cout << it << ' ';
return 0;
}