Pagini recente » Cod sursa (job #2677060) | Cod sursa (job #263321) | Cod sursa (job #454472) | Cod sursa (job #2753629) | Cod sursa (job #2673650)
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
vector<int> GetZ(string s) {
int n = s.length();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
z[i] = min(r - i + 1, z[i - l]);
if (z[i] < 0)
z[i] = 0;
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;
}
}
return z;
}
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string patt, text;
getline(cin, patt);
getline(cin, text);
string s = patt + "#" + text;
auto z = GetZ(s);
vector<int> ans;
for (int i = patt.size() + 1; i < (int)s.size(); ++i) {
if (z[i] == (int)patt.size()) {
ans.emplace_back(i - patt.size() - 1);
}
}
cout << ans.size() << '\n';
for (int x : ans) cout << x << ' ';
cout << endl;
}