Problem
In this problem, we’ll use the term “longest common substring” loosely. It refers to substrings differing at some number or fewer characters when compared index by index. For example, ‘abc’ and ‘adc’ differ in one position, ‘aab’ and ‘aba’ differ in two.
Given two strings and an integer, determine the length of the longest common substrings of the two strings that differ in no more than k positions.
Input
The first line of input contains a single integer, T, the number of test cases follow.
Each of the next T lines contains three space-separated values: an integer k and two strings, s1 and s2.
- k: an integer that represents the maximum number of differing characters in a matching pair
- s1: the first string
- s2: the second string
Output
For each test case, output a single integer which is the length of the maximum length common substrings differing at k or fewer positions.
Constraints
- 1 <= T <= 10
- 1 <= k <= | s1 |
- | s1 | = | s2 |
- 1 <= | s1 | , | s2 | <= 1500
Sample Input
3 2 tabriz torino 0 abacba abcaba 3 helloworld yellomarin
Sample Output
4 3 8
Explanation
Test Case #01: If we take “briz” from the first string, and “orin” from the second string, then the number of mismatches between these two substrings is equal to 2 and their lengths are 4.
Code Implementation
//
// main.cpp
// Substring Diff
//
// Created by Himanshu on 21/02/22.
//
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
int main() {
int T;
cin>>T;
while (T--) {
long ans = 0, k;
string p, q;
cin>>k>>p>>q;
int n = (int) p.size();
long *currk = new long [2*n+1]();
auto st = new long [2*n+1][2]();
long lcs[n+1][n+1];
memset(lcs, 0, sizeof(lcs[0][0]) * (n+1) * (n+1));
for (int i=0; i<=n; i++) {
for (int j=0; j<=n; j++) {
currk[i-j+n] = 0;
if (i >= j) {
st[i-j+n][0] = i-j+1;
st[i-j+n][1] = 1;
} else {
st[i-j+n][0] = 1;
st[i-j+n][1] = j-i+1;
}
}
}
for(int i=0; i<=n; i++) {
for(int j=0; j<=n; j++) {
//Longest Common Substring DP
if (i == 0 || j == 0) {
lcs[i][j] = 0;
currk[i-j+n] = 0;
} else if (p[i-1] == q[j-1]) {
lcs[i][j] = lcs[i-1][j-1] + 1;
} else if (p[i-1] != q[j-1]) {
lcs[i][j] = lcs[i-1][j-1] + 1;
currk[i-j+n]++;
}
//Sliding Window technique
if (currk[i-j+n] > k) {
long l, m, ctr = 0, flag = 0;
for(l=st[i-j+n][0], m=st[i-j+n][1]; l<i && m<j; l++, m++) {
ctr++;
if (p[l-1] != q[m-1]) {
flag = 1;
break;
}
}
if (flag) {
lcs[i][j] = lcs[i-1][j-1] - ctr + 1;
st[i-j+n][0] = l+1;
st[i-j+n][1] = m+1;
currk[i-j+n]--;
}
}
if (lcs[i][j] > ans) {
ans = lcs[i][j];
}
}
}
printf("%ld\n",ans);
}
return 0;
}
Time Complexity: O(n2)