fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Function to compute the Z-array
  9. vector<int> z_algorithm(const string &s) {
  10.     int n = s.size();
  11.     vector<int> z(n);
  12.     int l = 0, r = 0;
  13.  
  14.     for (int i = 1; i < n; ++i) {
  15.         if (i > r) {
  16.             l = r = i;
  17.             while (r < n && s[r] == s[r - l]) {
  18.                 r++;
  19.             }
  20.             z[i] = r - l;
  21.             r--;
  22.         } else {
  23.             int k = i - l;
  24.             if (z[k] < r - i + 1) {
  25.                 z[i] = z[k];
  26.             } else {
  27.                 l = i;
  28.                 while (r < n && s[r] == s[r - l]) {
  29.                     r++;
  30.                 }
  31.                 z[i] = r - l;
  32.                 r--;
  33.             }
  34.         }
  35.     }
  36.     return z;
  37. }
  38.  
  39. // Function to find the best starting index of the substring in text
  40. int find_best_substring(const string &text, const string &pattern) {
  41.     int n = text.size(), m = pattern.size();
  42.  
  43.     // Z-algorithm on pattern + "$" + text
  44.     string concat1 = pattern + "$" + text;
  45.     vector<int> z1 = z_algorithm(concat1);
  46.  
  47.     // Z-algorithm on reversed pattern + "$" + reversed text
  48.     string reversed_pattern = string(pattern.rbegin(), pattern.rend());
  49.     string reversed_text = string(text.rbegin(), text.rend());
  50.     string concat2 = reversed_pattern + "$" + reversed_text;
  51.     vector<int> z2 = z_algorithm(concat2);
  52.  
  53.     int max_length = -1;
  54.     int best_index = -1;
  55.  
  56.     // Find maximum overlap
  57.     for (int i = m + 1; i < z1.size(); ++i) {
  58.         int prefix_length = z1[i];
  59.         int suffix_length = (i - (m + 1) < z2.size()) ? z2[z2.size() - (i - (m + 1))] : 0;
  60.  
  61.         if (prefix_length + suffix_length >= m) {
  62.             int start_index = i - (m + 1);
  63.             if (prefix_length + suffix_length > max_length) {
  64.                 max_length = prefix_length + suffix_length;
  65.                 best_index = start_index;
  66.             }
  67.         }
  68.     }
  69.  
  70.     return best_index;
  71. }
  72.  
  73. int main() {
  74.     string text = "abcdefg";
  75.     string pattern = "bcdffg";
  76.  
  77.     int result = find_best_substring(text, pattern);
  78.     cout << "Best starting index: " << result << endl;
  79.  
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5260KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Best starting index: 0
https://ideone.com/Xbdftl
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!