有没有一种方法可以在O(NlogN)时间内找到两个序列的最长公共子序列?
我在某个地方看到过使用二分搜索实现这一点的方法。
我知道需要O(N2)时间的dp方法。
有没有一种方法可以在O(NlogN)时间内找到两个序列的最长公共子序列?
我在某个地方看到过使用二分搜索实现这一点的方法。
我知道需要O(N2)时间的dp方法。
动态规划方法适用于一般情况下的O(n2)。对于某些其他情况,存在更低复杂度的算法:
对于固定的字母表大小(不随n增长),有Four Russians方法,将时间降至O(n2/log n)(参见此处)。
请参见此处另一个进一步优化的情况。
两个序列之间的最长公共子序列基本上是n平方级别的。
Masek和Patterson(1980)使用所谓的“Four Russians”技术对n平方/ log n进行了轻微改进。
在大多数情况下,这种复杂的方法引入的额外复杂性并不能证明小幅收益。对于实际应用,您可以将n平方方法视为典型应用中合理的最优解。
vector <int> LIS;
int LongestIncreasingSubsequence(int n){
if(!n) return 0;
LIS.emplace_back(arr[0]);
for(int i = 1; i < n; i++){
if(arr[i] > LIS.back()) LIS.emplace_back(arr[i]);
else *lower_bound(LIS.begin(), LIS.end(), arr[i]) = arr[i];
}
return LIS.size();
}
//If the strings are not the same length, take the longest one
//Map each letter with a ArrayList representing the occurences on that letter (indexes)
//The ArrayLists are thus sorted. This will enable binary search later on
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < first.length(); i++) {
char c = first.charAt(i);
if (!map.containsKey(c)) {
map.put(c, new ArrayList<>());
}
map.get(c).add(i);
}
//Loop on the second string and increment an index to check that any matching character is a valid match
//For sequence match we need to maintain the same order as in the initial string so we use an increasing index for that
int index = 0;
StringBuilder lcs = new StringBuilder();
for (int j = 0; j < second.length(); j++) {
char c = second.charAt(j);
if (map.containsKey(c)) {
List<Integer> indexes = map.get(c);
//The following method uses Binary Search to find the first bigger or equal index
//This is possible since the indexes list is sorted by definition
int firstBigger = firstBiggerOrEqualIndex(indexes, index);
if (firstBigger != -1) {
index = firstBigger+1;
lcs.append(c);
}
}
}
return lcs.toString();
方法 firstBiggerOrEqualIndex 使用类似二分查找的方式:
private static int firstBiggerOrEqualIndex(List<Integer> indexes, int index) {
int start = 0;
int end = indexes.size()-1;
int res = -1;
while(start <= end) {
int mid = (start+end)/2;
int value = indexes.get(mid);
if (value > index) {
res = value;
end = mid-1;
}
else if (value == index) {
res = value;
break;
}
else {
start = mid + 1;
}
}
return res;
}