Pagini recente » Cod sursa (job #2215914) | Cod sursa (job #842232) | Cod sursa (job #2544037) | Cod sursa (job #1314387) | Cod sursa (job #1968129)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, S;
vector < int > phi;
int ans;
vector < int > all;
void input() {
fin >> s >> S;
s = ' ' + s; S = ' ' + S;
}
void compute_phi(string s) {
int k = 0;
phi = vector < int > (s.size(), 0);
for (int i = 2; s[i]; ++i) {
while (k && s[k+1] != s[i])
k = phi[k];
if (s[k+1] == s[i]) k++;
phi[i] = k;
}
}
void compute_answer(string S, string s) {
int k = 0;
for (int i = 1; S[i]; ++i) {
while (k && s[k+1] != S[i])
k = phi[k];
if (s[k+1] == S[i]) k++;
if (s[k+1] == 0) {
ans++;
if (ans <= 1000) all.push_back(i-k);
}
}
}
void output() {
fout << ans << '\n';
for (auto &it: all) fout << it << ' ';
fout << '\n';
}
int main() {
input();
compute_phi(s);
compute_answer(S, s);
output();
return 0;
}