Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- vector<int> z_f(string s){
- int n = s.size();
- int R = 0;
- int L = 0;
- vector<int> Z(n, 0);
- for (int i = 1; i < n; ++i) {
- if (i > R) {
- // calculating new substring
- L = R = i;
- while (s[R] == s[R - L] && R < n) {
- R++;
- }
- R--;
- Z[i] = R - L + 1;
- // calculated
- } else {
- // we are inside substring
- if (Z[i - L] < R - i + 1) {
- Z[i] = Z[i - L];
- } else {
- // we might be inside our own substring like in last character of "abcabca" (its not 4)
- L = i;
- while (s[R] == s[R - L] && R < n) {
- R++;
- }
- R--;
- Z[i] = R - L+1;
- }
- }
- }
- return Z;
- }
- void display(const vector<int> &v){
- for (const auto& e : v){
- cout << e%10 << " ";
- }
- cout << endl;
- }
- int main (){
- string pattern;
- string input;
- cin >> pattern >> input;
- string s1 = pattern+"@"+input;
- string s2 = input+"@"+pattern;
- reverse(s2.begin(), s2.end());
- vector<int> z_v = z_f(s1);
- z_v = {z_v.begin()+pattern.size()+1, z_v.end()};
- vector<int> z_r_v = z_f(s2);
- z_r_v = {z_r_v.begin() + pattern.size() + 1, z_r_v.end()};
- reverse(z_r_v.begin(), z_r_v.end());
- vector<int> occurrences;
- int l = 0, r = pattern.size()-1;
- while (r<input.size()){
- if (z_v[l] + z_r_v[r] >= pattern.size()-1){
- occurrences.push_back(l+1);
- }
- ++l;
- ++r;
- }
- cout << occurrences.size() << endl;
- for (const auto& e : occurrences){
- cout << e << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement