C++中查找 S1 中在给定代价下与 S2 匹配的最长子串

banq
给定两个长度为n的字符串S1和S2。另外，两个正整数target和 C。任务是确定S1中连续子串的最大长度，以便通过将S1子串中的任何字符更改为另一个字符，得到的子串与S2中的相应段匹配，这些变化的总成本最多为target，其中每个角色的转换成本为C个单位。

注意：如果存在多个具有相同最大长度的有效子字符串，请提供其中任何一个作为答案。

例如：
输入： S1 = “abcd”, S2 = “bcdf”, C = 1, target = 3
输出： 1 3
解释： S1 中索引 1 到 3 的子字符串是“bcd”，可以更改为“cdf”。更改的成本为 3。因此最大长度为 3。

方法：
这个想法是使用答案上的二进制搜索方法来查找最大可能长度。对于每个潜在长度（从当前搜索范围 [start, end] 的中点开始），使用滑动窗口方法来检查S1中该长度（即mid）的所有子串。计算每个子字符串的转换成本并检查它是否小于或等于 target。如果找到有效的子字符串，则更新起始位置和结束位置，并以更大的长度继续搜索。如果未找到特定长度的有效子字符串，则以较小的长度继续搜索。

分步方法：

  • 以可能的最小有效长度子字符串（即 0）开始初始化变量。
  • 使用可能的最大有效长度子字符串（即字符串本身的大小）初始化变量end 。
  • 初始化一个变量result，用于存储有效子串的最大长度
  • 当start小于end时，执行以下操作：
    • 计算mid = (start + end) /2
    • 检查mid是否是有效子字符串的可能长度
      • 将结果分配给mid
      • 将start移至mid + 1。
    • 否则，将end移至mid。
  • 如果可能存在任何有效子字符串，则打印有效子字符串的起始索引和结束索引。

C++代码:

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

// 初始化 S1 变量 startPos 和 endPos，分别用于存储有效子串 
//  的起始和终止位置。
int startPos = -1, endPos = -1;

bool isValid(int len, string& S1, string& S2, int C, int target)
{
    int i = 0, j = 0, n = S1.size(), cost = 0;

   // 将 S1 变量标志初始化为 false。
    //它会跟踪任何长度为 len 的有效子串是否可能。
    bool flag = false;

    while (j < n) {

        // 包括将 S1[j] 转换为 S2[j] 所需的费用
        cost += ((S1[j] != S2[j]) ? C : 0);

        //如果窗口大小等于 len，则移动窗口。
        if (j - i + 1 == len) {

// 检查是否存在有效子串，然后将有效子串的索引保留在 startPos 和 endPos 中
            if (cost <= target) {
                flag = true;
                startPos = i;
                endPos = j;
            }

            //移除计算
     //用指数作为我们的窗口
      //我们必须滑动我们的窗口
            cost -= ((S1[j] != S2[j]) ? C : 0);
            i++;
        }

        j++;
    }

    // Return the flag
    return flag;
}

void validSubstring(string S1, string S2, int C, int target)
{
    startPos = -1, endPos = -1;

    // 初始化 S1 变量以
    // 最小有效长度
    // 可能的子串。
    int start = 0;

    // 初始化 S1 变量，以
    //可能的最大有效长度子串
    //结束。
    int end = S1.size();
    int n = S1.size();

    // 初始化 S1 变量结果，用于
    // 存储
    // 有效子串的最大长度。
    int result = 0;

    // 在起点小于终点时执行
    // 小于等于终点时执行。
    while (start < end) {

        // Calculate the mid
        int mid = (start + end) / 2;

       // 检查 mid 是否为可能的长度
      // 为有效子串
        if (isValid(mid, S1, S2, C, target)) {

            // Assign result to mid
            result = mid;

            // Shift start to mid + 1
            start = mid + 1;
        }

        // Otherwise shift end to mid - 1
        else {
            end = mid;
        }
    }

    if (startPos == -1)
        cout << "Not possible\n";
    else
        cout << startPos << " " << endPos << "\n";
}

// Driver code
int main()
{
    // First test case
    string S1 = "abcd", S2 = "bcdf";
    int C = 1, target = 5;
    validSubstring(S1, S2, C, target);
    
    // Second test case
    S1 = "abc", S2 = "cdf";
    C = 10, target = 3;
    validSubstring(S1, S2, C, target);

    // Third test case
    S1 = "abcb", S2 = "cdfb";
    C = 2, target = 2;
    validSubstring(S1, S2, C, target);

    return 0;
}

时间复杂度： O(N* log(N))辅助空间： O(1)