1371 Period

題目說明

給兩個字串A,B，可以把B分成好幾份子字串，A與每一段的字串的最短編輯距離的最大值為k，求k的最小值 exp: A="abc" B="abbbcabc" 分割方法為 B->"ab","bbc","abc"(編輯距離分別為 1,1,0 )最大編輯距離為1，這是所有分割法中，能分割出最小的最大值

解題過程

最短編輯距離edit-distance(ED)的dp式與LCS的精神類似 dp式: dp[i][j]:a在前i個字與b在前j個字的ED if a[i-1]==b[i-1]: dp[i][j]=dp[i-1][j-1]如果最後一個字元相同，那麼這個字串的ED就等於加上這個字元前的字串ED前的字串ED else: dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])否則就輸出改變次數最少的那個來+1 使用二分搜尋，來搜尋B序列是否可被分割後，最大子序列小於某個數字，如果可以就縮小數字，否則就提高數字 而一開始，可以先將這個數字設為A跟B比較的最大長度，再漸漸用二分搜尋去找。 至於要怎麼去找B序列被分割後會不會大於某數:

假設B有個子區間，開頭為Bs，結尾為Be，某數為m 用動態規劃的方式，bool dp[i]代表B的前i個字的序列的切割編輯距離能不能<=m

然後我們再遍歷B的所有區間: 如果這個區間的切割編輯距離竟然<=m 而且 Bs前面的序列的切割編輯距離(已經動態規劃紀錄的部分)竟然也可以，那麼: Be前面就是可以被切割的(dp[i]=true) 到最後，輸出整個B的切割編輯距離可不可以<=m

程式碼

#include <climits>
#include <iostream>
using namespace std;
int ED(string a, string b) {
  int dp[a.length() + 1][b.length() + 1];
  for (int i = 0; i <= b.length(); i++) dp[0][i] = i;
  for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
  for (int i = 1; i <= a.length(); i++)
    for (int j = 1; j <= b.length(); j++)
      if (a[i - 1] == b[j - 1])
        dp[i][j] = dp[i - 1][j - 1];
      else
        dp[i][j] = 1 + min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
  return dp[a.length()][b.length()];
}

int isValid(const string& A, const string& B, int maxDist) {
  int n = B.length();
  int dp[n + 1];
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    dp[i] = 0;
    for (int j = 0; j < i; j++) {
      string part = B.substr(j, i - j);
      if (ED(A, part) <= maxDist && dp[j]) dp[i] = 1;
    }
  }
  return dp[n];
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    string A, B;
    cin >> A >> B;
    int left = 0, right = max(A.length(), B.length()), ans = right;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (isValid(A, B, mid)) {
        ans = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}