Pagini recente » Cod sursa (job #2327714) | Cod sursa (job #541642) | Cod sursa (job #455790) | Cod sursa (job #1039045) | Cod sursa (job #1967070)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string pat, str, cat;
vector<int> aps;
int ant;
int z[1 << 21];
void make_z(const string &str, int z[]) {
int n = str.size();
for (int l, i = 1, r = 0; i < n; ++i) {
if (i > r) {
for (l = r = i; str[r - l] == str[r]; ++r);
z[i] = r - l;
--r; }
else {
z[i] = min(z[i - l], r - i + 1);
if (i + z[i] >= r) {
for (l = i; str[r - l] == str[r]; ++r);
z[i] = r - i;
--r; } } } }
int main() {
fi >> pat >> str;
cat = pat + "#" + str;
make_z(cat, z);
for (int i = 0; i < cat.size(); ++i)
if (z[i] >= pat.size())
if (++ant <= 1000)
aps.push_back(i - pat.size() - 1);
fo << ant << '\n';
for (auto i: aps)
fo << i << ' ';
fo << '\n';
return 0; }