C++ 在给定字符串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}索引来获得相邻索引之间的最大差值。

方法

在这种方法中，我们将按照实际顺序找到子序列的索引。之后，我们将按相反的顺序找到子序列的索引。我们将实际索引减去反向索引，以获得最大差值。

通过下面的示例来理解该方法。

str = “bbbbbbb”, sub = “bbb”;

• 当我们按照实际顺序找到子序列的索引时，我们将得到{0, 1, 2}索引。

• 当我们按照相反顺序找到子序列的索引时，我们将得到{4, 5, 6}索引。

• 最后，我们将相反索引-实际索引[p + 1] = 6 – 1 = 5。同样，5 – 0 = 5。因此，通过这种方式，我们可以得到最大的相邻索引差。

算法

第1步 - 定义’max_diff’变量来存储最大相邻索引差值。还要定义leftInd和rightInd数组，长度与子字符串长度相等，用于存储从左到右的子序列的索引。

第2步 - 开始遍历给定的字符串。如果指向’sub’字符串的指针大于字符串长度，则退出循环。

第3步 - 如果字符串中第pth索引的字符和’sub’字符串中的sub_ind索引处的字符相同，将p的值赋给’leftInd’数组，并递增sub_ind指针。

第4步 - 使用子字符串长度-1初始化sub_ind指针，并以相反的顺序遍历字符串。

第5步 - 如果sub_ind小于0，则退出循环。此外，如果字符串的字符和’sub’匹配，则更新’rightInd’数组，并将’sub_ind’值减1。

第6步 - 遍历’leftInd’和’rightInd’数组。如果rightInd[p + 1] – leftInd[p]大于maxDiff变量的值，则更新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) 用于存储子序列的索引。

我们可以选择任何子序列的出现，并找到其相邻索引之间的最大差值。程序员应该使用不同的输入对代码进行测试，以更好地理解问题及其解决方案。