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<iostream>
#include<climits>
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;
}