Pagini recente » Cod sursa (job #919494) | Cod sursa (job #860577) | Cod sursa (job #3237003) | Cod sursa (job #1868324) | Cod sursa (job #3156160)
#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 + 5, 0);
for (int i = 1; i < n; ++i) {
if (i < r) {
z[i] = max(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 (ans.size() + 1 <= 1000)
ans.emplace_back(i - pat.size() - 1);
}
fout << cnt << '\n';
for (auto i : ans)
fout << i << ' ';
}