給定字串S中存在的子序列T的最大相鄰索引差

---

在這個問題中，我們需要找到給定字串中存在的子序列的索引之間的最大差值。

為了解決這個問題，我們需要找到子序列在實際順序和反向順序中的索引。之後，我們需要取兩者的差值。

問題陳述 - 我們給定兩個名為“str”和“sub”的字串。“sub”字串始終作為子序列存在於“str”字串中。我們需要找到最大索引成本。索引成本是子序列的兩個索引之間的差值。

示例

輸入

str = "deeer", sub = "der"

輸出

3

解釋

• 我們可以使用{0, 1, 4}、{0, 2, 4}和{0, 3, 4}來獲取“sub”。

• 因此，如果我們取集合{0, 1, 4}，我們可以得到最大相鄰索引差，即4 - 1 == 3。

輸入

str = "abcdef", sub = "acf"

輸出

3

解釋

• 子序列存在於{0, 2, 5}索引處。因此，索引之間的最大差值為5 - 2 = 3。

輸入

str = "bbbbbbb", sub = "bb";

輸出

6

解釋 - 我們可以取子序列的{0, 6}索引來獲得相鄰索引之間的最大差值。

方法1

在這種方法中，我們將按照實際順序查詢子序列索引。之後，我們將按照反向順序查詢子序列索引。我們將從反向索引中減去實際索引以獲得最大差值。

讓我們透過下面的例子來理解這種方法。

str = "bbbbbbb", sub = "bbb";

• 當我們按照實際順序查詢子序列索引時，我們將得到{0, 1, 2}索引。

• 當我們按照反向順序查詢子序列索引時，我們將得到{4, 5, 6}。

• 最後，我們將減去reverse[p + 1] - actual[p] = 6 - 1 = 5。同樣，5 - 0 = 5。這樣，我們可以得到最大相鄰索引差。

演算法

步驟1 - 定義'max_diff'變數來儲存最大相鄰索引差。另外，定義長度等於子字串長度的leftInd和rightInd陣列來儲存子序列的索引，分別從左到右。

步驟2 - 開始遍歷給定的字串。如果指向“sub”字串的指標大於字串長度，則中斷迴圈。

步驟3 - 如果字串中第p個索引處的字元和“sub”字串中sub_ind索引處的字元相同，則將p值賦給“leftInd”陣列並遞增sub_ind指標。

步驟4 - 將sub_ind指標初始化為子字串長度 - 1，並開始反向遍歷字串。

步驟5 - 如果sub_ind小於0，則中斷迴圈。此外，如果字串的字元和“sub”匹配，則更新“rightInd”陣列並將“sub_ind”值減1。

步驟6 - 遍歷“leftInd”和“rightInd”陣列。如果rightInd[p + 1] - leftInd[p]大於它，則更新maxDiff變數的值。

步驟7 - 返回“maxDiff”值。

示例

#include <bits/stdc++.h>
using namespace std;

int findMaxIndexDiff(string str, string sub, int str_len, int sub_len) {
   // to store maximum index difference
   int maxDiff = 0;
   // to store minimum and maximum possible values of the character index
   int leftInd[sub_len], rightInd[sub_len];

   // pointer for substring
   int sub_ind = 0;
   // traverse the string
   for (int p = 0; p < str_len; p++) {
      if (sub_ind >= sub_len)
         break;
// store the left-most index of the character of a substring in the given string
      if (str[p] == sub[sub_ind]) {
         leftInd[sub_ind] = p;
         sub_ind++;
      }
   }
   sub_ind = sub_len - 1;
   for (int p = str_len - 1; p >= 0; p--) {
      if (sub_ind < 0)
         break;
      // Storing right-most index of character
      if (str[p] == sub[sub_ind]) {
         rightInd[sub_ind] = p;
         sub_ind--;
      }
   }
   for (int p = 0; p < sub_len - 1; p++){
      // Getting the maximum difference
      maxDiff = max(maxDiff, rightInd[p + 1] - leftInd[p]);
   }
   // Return the final answer
   return maxDiff;
}
int main() {
   string str = "deeer", sub = "der";
   int str_len = str.length(), sub_len = sub.length();
   cout << "The maximum index difference for a subsequence present in the given string is " << findMaxIndexDiff(str, sub, str_len, sub_len);
   return 0;
}

輸出

The maximum index difference for a subsequence present in the given string is 3

時間複雜度 - O(n + m) 用於遍歷字串和子序列索引陣列。

空間複雜度 - O(M) 用於儲存子序列的索引。

我們可以取子序列的任何出現並找到其相鄰索引之間的最大差值。程式設計師應該使用不同的輸入測試程式碼，以便更好地理解問題及其解決方案。