Pagini recente » Cod sursa (job #2051782) | Cod sursa (job #2742873) | Cod sursa (job #2840159) | Cod sursa (job #482681) | Cod sursa (job #2798219)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector<int> Z(string &s) {
vector<int> z((int)s.size());
z[0] = 0;
int r = -1, l = -1;
for (int i = 1; i < (int)s.size(); i++) {
if (i <= r)
z[i] = min(z[i - l], r - i + 1);
while (z[i] + i < (int)s.size() && s[z[i]] == s[z[i] + i])
z[i]++;
if (z[i] + i - 1 > r) {
r = z[i] + i - 1;
l = i;
}
}
return z;
}
int main() {
in.tie(NULL);
out.tie(NULL);
ios_base::sync_with_stdio(false);
string p, s; in >> p >> s;
p = p + '#' + s;
auto z = Z(p);
vector<int> app;
for (int i = 0; i < (int)p.size(); i++)
if (z[i] == (int)p.size() - (int)s.size() - 1)
app.push_back(i - ((int)p.size() - (int)s.size()));
out << (int)app.size() << "\n";
for (int i = 0; i < min((int)app.size(), 1000); i++)
out << app[i] << " ";
return 0;
}