Pagini recente » Cod sursa (job #1670438) | Cod sursa (job #2760998) | Cod sursa (job #1183563) | Cod sursa (job #2644645) | Cod sursa (job #3156339)
#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, 0);
for(int i = 2, l = 1, r = 1; i < n; i++) {
if(i <= r) {
z[i] = min(r - i, z[i - l]);
}
while(i + z[i] < n && s[z[i] + 1] == 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 + 1; i < m; i++) {
if(z[i] == n) {
cnt++;
if(cnt <= 1000) {
ans.emplace_back(i - n - 2);
}
}
}
fout << cnt << '\n';
for(const auto &it: ans) {
fout << it << " ";
}
return 0;
}