Pagini recente » Cod sursa (job #700868) | Cod sursa (job #2980930) | Cod sursa (job #3246593) | Cod sursa (job #1726138) | Cod sursa (job #2702597)
#include <string>
#include <fstream>
#include <vector>
using namespace std;
vector<int> build_kmp_table(string w);
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
fin >> a >> b;
int na = a.length();
int nb = b.length();
vector<int> t = build_kmp_table(a);
vector<int> results;
results.reserve(nb-na+1);
int s = 0;
int i = 0;
while (s < nb) {
if (i == na) {
results.push_back(s);
s = s + i - t[i-1];
i = t[i-1];
}
else if (b[s+i] == a[i]) {
++i;
}
else if (i == 0) {
s++;
}
else {
s = s + i - t[i-1];
i = t[i-1];
}
}
fout << results.size() << endl;
for (int pos : results)
fout << pos << ' ';
fout << endl;
return 0;
}
vector<int> build_kmp_table(string w)
{
int n = w.length();
vector<int> t(n,-1);
t[0] = 0;
for (int i = 1; i < n; ++i) {
int k = t[i-1];
while (t[i] == -1) {
if (k == 0)
t[i] = w[i] == w[0] ? 1 : 0;
else if (w[i] == w[k])
t[i] = k+1;
else
k = t[k-1];
}
}
return t;
}