Pagini recente » Cod sursa (job #829782) | Cod sursa (job #2302316) | Cod sursa (job #996294) | Cod sursa (job #901123) | Cod sursa (job #3144421)
#include <fstream>
#include <vector>
using namespace std;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
f >> a >> b;
vector<int> p(a.length());
p[0] = 1;
int pos = 0;
for (int i = 1; i < a.length(); ++i) {
while (pos > 0 && a[pos] != a[i])
pos = p[pos];
if (a[pos] == a[i]) {
p[i] = pos + 1;
pos += 1;
}
else {
p[i] = 0;
pos = 0;
}
}
int i = 0, j = 0;
vector<int> match_pos;
while (j < b.length()) {
if (match_pos.size() == 1000)
break;
if (a[i] == b[j]) {
if (i == a.length() - 1) {
match_pos.push_back(j - a.length() + 1);
i = p[i];
}
else
++i;
++j;
}
else if (i == 0)
++j;
else
i = p[i];
}
g << match_pos.size() << "\n";
for (auto pos : match_pos)
g << pos << " ";
return 0;
}