Pagini recente » Cod sursa (job #713191) | Cod sursa (job #422814) | Istoria paginii runda/onishor | Cod sursa (job #1269742) | Cod sursa (job #185873)
Cod sursa(job #185873)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void prefix ( const string &a, vector<int> &pi ) {
pi.resize(a.size());
pi[0] = -1;
int i;
int k;
for (i = 1, k = -1; i < a.size(); ++i) {
for (; k >= 0 && a[i] != a[k+1]; k = pi[k]);
if (a[i] == a[k+1]) {
++k;
pi[i] = k;
} else {
pi[i] = -1;
}
}
}
void search ( const string &what, const string &where, vector<int> &ret ) {
vector<int> pi;
prefix(what,pi);
for (int i = 0, k = -1; i < where.size(); ++i) {
// fout << i << ": k = " << k;
for (; k >= 0 && where[i] != what[k+1]; k = pi[k]);
// fout << " -> " << k << "\n";
if (where[i] == what[k+1]) {
++k;
if (k == what.size()-1) {
ret.push_back(i-k);
k = pi[k];
}
} else {
k = -1;
}
}
}
int main() {
string a,b;
fin >> a >> b;
vector<int> ap;
search(a,b,ap);
fout << ap.size() << "\n";
for (int i = 0; i < ap.size() && i < 1000; ++i) fout << ap[i] << " ";
return 0;
}