Pagini recente » Cod sursa (job #2998345) | Cod sursa (job #2991309) | Cod sursa (job #1847008) | Cod sursa (job #1529163) | Cod sursa (job #2909786)
#include <bits/stdc++.h>
using namespace std;
int T;
void fast() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
vector<int> prefixKMP(const string &s) {
vector<int> pr(s.size() + 1);
pr[0] = -1;
for (size_t i = 1; i <= s.size(); i++) {
int k = pr[i - 1];
while (k >= 0 && s[k] != s[i - 1]) {
k = pr[k];
}
pr[i] = k + 1;
}
return pr;
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
fin >> A >> B;
string concat = A + '#' + B;
vector<int> pr = prefixKMP(concat);
vector<int> ap;
for (int i = (int) A.size() + 1; i < (int) concat.size(); i++) {
if (pr[i] == A.size())
ap.push_back(i - (int) A.size() * 2 - 1);
}
fout << ap.size() << '\n';
for (int i = 0; i < min((int) ap.size(), 1000); i++)
fout << ap[i] << ' ';
return 0;
}