我需要构建一个算法(不一定有效),给定一个字符串找到并打印两个相同的子序列(通过打印,我的意思是颜色).此外,这两个子序列的索引集合的联合必须是一组连续的自然数(整数的整数).
在数学中,我正在寻找的东西被称为“紧身双胞胎”,如果它有帮助的话. (例如,参见paper (PDF) here.)
我举几个例子：
1)考虑字符串231213231
它有两个子序列,我正在寻找“123”的形式.要更好地查看此图片：
第一个子序列标有下划线,第二个子序列标有上划线.如你所见,他们拥有我需要的所有属性.
2)考虑字符串12341234
3)考虑字符串12132344.
现在它变得更加复杂：
4)考虑字符串：13412342
它也不是那么容易：
我认为这些例子很好地解释了我的意思.
我一直在思考一个可以做到这一点但却没有成功的算法.
为了着色,我想使用这段代码：
using namespace std;
HANDLE hConsole;
hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hConsole,k);
其中k是颜色.
任何帮助,甚至提示,都将受到高度赞赏.
解决方法
这是一个简单的递归,测试紧身双胞胎.当存在重复时,它会拆分决策树,以防副本仍然是第一个双胞胎的一部分.你必须在偶数长度的每个子串上运行它.对较长子串的其他优化可能包括对char计数进行散列测试,以及匹配候选双胞胎的非重复部分(仅在整个子字符串中出现两次的字符).
功能说明：
首先,创建一个散列,每个字符作为键,索引以值的形式出现.然后我们遍历哈希：如果字符计数是奇数,则该函数返回false;并且计数大于2的字符的索引被添加到重复列表中 – 其中一半字符属于一个双胞胎,但我们不知道哪个.
递归的基本规则是仅在字符串中稍后找到匹配时增加i,同时保持所选匹配(js)的记录,我必须跳过该记录而不查找匹配.这是有效的,因为如果我们找到n / 2个匹配,按顺序,到j到达结尾时,这基本上只是另一种说法是字符串由紧孪生组成的方式.
JavaScript代码：
function isTightTwins(s){
var n = s.length,char_idxs = {};
for (var i=0; i<n; i++){
if (char_idxs[s[i]] == undefined){
char_idxs[s[i]] = [i];
} else {
char_idxs[s[i]].push(i);
}
}
var duplicates = new Set();
for (var i in char_idxs){
// character with odd count
if (char_idxs[i].length & 1){
return false;
}
if (char_idxs[i].length > 2){
for (let j of char_idxs[i]){
duplicates.add(j);
}
}
}
function f(i,j,js){
// base case positive
if (js.size == n/2 && j == n){
return true;
}
// base case negative
if (j > n || (n - j < n/2 - js.size)){
return false;
}
// i is not less than j
if (i >= j) {
return f(i,j + 1,js);
}
// this i is in the list of js
if (js.has(i)){
return f(i + 1,js);
// yet to find twin,no match
} else if (s[i] != s[j]){
return f(i,js);
} else {
// maybe it's a twin and maybe it's a duplicate
if (duplicates.has(j)) {
var _js = new Set(js);
_js.add(j);
return f(i,js) | f(i + 1,_js);
// it's a twin
} else {
js.add(j);
return f(i + 1,js);
}
}
}
return f(0,1,new Set());
}
console.log(isTightTwins("1213213515")); // true
console.log(isTightTwins("11222332")); // false
