Pagini recente » Cod sursa (job #687832) | Cod sursa (job #3162264) | Cod sursa (job #328190) | Cod sursa (job #2894360) | Cod sursa (job #2178212)
#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 && (int)ret.size() < 1000; ++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(auto x: ans) fout << x << " ";
return 0;
}