Pagini recente » Cod sursa (job #1789168) | Cod sursa (job #1598655) | Cod sursa (job #3039458) | Cod sursa (job #683727) | Cod sursa (job #3156169)
#include <bits/stdc++.h>
using namespace std;
string const TASKNAME("strmatch");
ifstream fin(TASKNAME + ".in");
ofstream fout(TASKNAME + ".out");
string str, pat;
vector<int> Z() {
int n = str.size();
int l = 0, r = 0;
vector<int> z(n, 0);
for (int i = 1; i < n; ++i) {
if (i < r) {
z[i] = min(r - i, z[i - l]);
}
while (i + z[i] < n && str[z[i]] == str[i + z[i]])
++z[i];
if (i + z[i] > r) {
r = i + z[i];
l = i;
}
}
return z;
}
int main() {
fin >> pat >> str;
str = pat + "$" + str;
vector<int> z = Z();
vector<int> ans;
int cnt = 0;
for (int i = pat.size() + 1; i < str.size(); ++i)
if (z[i] == pat.size()) {
++cnt;
if ((int)ans.size() < 1000)
ans.emplace_back(i - pat.size() - 1);
}
fout << cnt << '\n';
for (auto i : ans)
fout << i << ' ';
}