Pagini recente » Cod sursa (job #2954375) | Cod sursa (job #2886104) | Cod sursa (job #1386251) | Cod sursa (job #46004) | Cod sursa (job #3125859)
#include <bits/stdc++.h>
using namespace std;
const string taskname("strmatch");
ifstream fin(taskname + ".in");
ofstream fout(taskname + ".out");
vector<int> ZFun(string s, string pattern) {
s = pattern + "@" + s;
int n = s.size();
vector<int> Z(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i <= r)
Z[i] = min(Z[i - l], r - i + 1);
while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]])
++Z[i];
if (i + Z[i] - 1 > r)
l = i, r = i + Z[i] - 1;
}
vector<int> trimmedZ;
for (int i = pattern.size() + 1; i < n; ++i)
trimmedZ.emplace_back(Z[i]);
return trimmedZ;
}
int main() {
string pattern, s;
fin >> pattern >> s;
vector<int> Z = ZFun(s, pattern);
int cntMatch = 0;
vector<int> idx;
for (int i = 0; i < s.size(); ++i) {
if (Z[i] == pattern.size()) {
++cntMatch;
if (cntMatch <= 1000)
idx.emplace_back(i);
}
}
fout << cntMatch << '\n';
for (auto pos : idx)
fout << pos << ' ';
}