在最多 T 成本下，將 A 的最長子串更改為 B 的子串

#include <stdio.h>
#include <string.h>

// Starting and ending position of valid substring
int st_ind = -1, end_ind = -1;

int isMidValid(int midLen, char A[], char B[], int K, int T) {
   int p = 0, q = 0, len = strlen(A), ct = 0;
   // To track whether any substring of length MidLen is valid
   int isValid = 0;
   while (q < len) {
      // Cost for converting one character to another
      ct += (A[q] != B[q]) ? K : 0;
      // Shifting the window to the right
      if (q - p + 1 == midLen) {
         // For cost less than T
         if (ct <= T) {
            isValid = 1;
            st_ind = p;
            end_ind = q;
         }
         // Removing the left character from the window
         ct -= (A[p] != B[p]) ? K : 0;
         p++;
      }
      q++;
   }
   // Output
   return isValid;
}

void printLongestSubstr(char A[], char B[], int K, int T) {
   st_ind = -1, end_ind = -1;

   // Left and right pointers for binary search
   int left = 0;
   int right = strlen(A) + 1;

   // To store the maximum length
   int maxLen = 0;
   while (left < right) {
      // Mid calculation
      int midLen = (left + right) / 2;
      // If midLen length is valid
      if (isMidValid(midLen, A, B, K, T)) {
         // Update max length
         maxLen = midLen;
         // Find the maximum length in the right half
         left = midLen + 1;
      } else {
         // If mid is invalid, then find in the left half
         right = midLen;
      }
   }
   if (st_ind == -1)
      printf("Not possible\n");
   else
      printf("Starting index - %d ending index - %d\n", st_ind, end_ind);
}

int main() {
   char A[] = "wxyz";
   char B[] = "wpqt";
   int K = 2, T = 5;
   printLongestSubstr(A, B, K, T);
   return 0;
}

輸出

Starting index - 0 ending index - 2