Pagini recente » Cod sursa (job #488851) | Cod sursa (job #2795460) | Cod sursa (job #1790050) | Cod sursa (job #452090) | Cod sursa (job #2178216)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector < int > zFind(const string &A, const string &B) {
string eval = A + "$" + B;
int n = (int)eval.size();
vector < int > aux(n);
for(int i = 1, lo = 0, hi = 0; i < n; ++i) {
if(i > hi) {
lo = hi = i;
while(i + aux[i] < n && eval[aux[i]] == eval[lo + aux[i]]) {
++aux[i];
++hi;
}
--hi;
} else {
if(i + aux[i - lo] > hi) {
lo = i;
aux[i] = hi - i;
while(i + aux[i] < n && eval[aux[i]] == eval[lo + aux[i]]) {
++aux[i];
++hi;
}
--hi;
} else {
aux[i] = aux[i - lo];
}
}
}
vector < int > ret;
for(int i = 0; i < n; ++i) {
if(aux[i] == (int)A.size()) {
ret.push_back(i - (int)A.size() - 1);
}
}
return ret;
}
int main() {
string A, B;
fin >> A >> B;
vector < int > ans = zFind(A, B);
fout << (int)ans.size() << "\n";
for(int i = 0; i < min((int)ans.size(), 1000); ++i) fout << ans[i] << " ";
return 0;
}