We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Substring Diff
  5. Discussions

Substring Diff

  • dehaka
     + 0 comments

    a modified version of the method for longest common substring, O(nm), each step in the matrix M takes constant time

    for each i,j, this finds the longest consecutive common substring of s1, s2, ending at s1[i] and s2[j], then it takes the max of all these length

    void dehaka(vector<vector<int>>& M, queue<int>& Q, int k, int i, int j) {
    if (Q.size() < k) {
        M[i][j] = M[i-1][j-1] + 1;
        Q.push(max(i, j));
    }
    else if (Q.size() == k) {
        M[i][j] = max(i, j) - Q.front();
        Q.pop();
        Q.push(max(i, j));
    }
}

int substringDiff(int k, string s1, string s2) {
    int answer = 0;
    vector<vector<int>> M(s1.size()+1, vector<int>(s2.size()+1, 0));
    vector<queue<int>> QS1(s1.size()), QS2(s2.size());
    for (int i=1; i <= s1.size(); i++) {
        for (int j=1; j <= s2.size(); j++) {
            if (s1[i-1] == s2[j-1]) M[i][j] = M[i-1][j-1] + 1;
            else if (i >= j and k > 0) {
                dehaka(M, QS1[i-j], k, i, j);
            }
            else if (i < j and k > 0) {
                dehaka(M, QS2[j-i], k, i, j);
            }
            answer = max(answer, M[i][j]);
        }
    }
    return answer;
}