Pagini recente » Cod sursa (job #893160) | Cod sursa (job #606681) | Cod sursa (job #875756) | Cod sursa (job #2544237) | Cod sursa (job #1966875)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int NMAX = 1 << 21;
vector<int> aps;
string a, b, c1, c2;
int n, m, q, apps;
int z[NMAX];
void make_z(const string &s, int z[]) {
int n = s.size();
for (int i = 1, l = 1, r = 0; i < n; ++i) {
if (i > r)
l = r = i;
z[i] = min(z[i - l], n - i);
for (; s[z[i]] == s[i + z[i]]; ++z[i]);
if (i + z[i] > r) {
l = i;
r = i + z[i]; } } }
int main() {
string str, pat;
fi >> pat >> str;
str = pat + "#" + str;
make_z(str, z);
for (int i = 1; i < str.size(); ++i)
if (z[i] == pat.size()) {
++apps;
if (apps <= 1000)
aps.push_back(i - pat.size() - 1); }
fo << apps << '\n';
for (auto i: aps)
fo << i << ' ';
fo << '\n';
return 0; }