Pagini recente » Cod sursa (job #522443) | Cod sursa (job #3156340)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> z_function(const string &s) {
int n = s.size();
vector<int> z(n);
for(int i = 1, l = 0, r = 0; i < n; i++) {
if(i <= r) {
z[i] = min(r - i, z[i - l]);
}
while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if(i + z[i] > r) {
r = i + z[i];
l = i;
}
}
return z;
}
int main() {
string t, s;
fin >> t >> s;
int n = t.size();
s = t + "@" + s;
int m = s.size();
vector<int> z = z_function(s);
int cnt = 0;
vector<int> ans;
for(int i = n; i < m; i++) {
if(z[i] == n) {
cnt++;
if(cnt <= 1000) {
ans.emplace_back(i - n - 1);
}
}
}
fout << cnt << '\n';
for(const auto &it: ans) {
fout << it << " ";
}
return 0;
}