给定一个字符串,找到两个具有连续索引C++的相同子序列

Question

我需要构建一个算法(不一定有效),给定一个字符串找到并打印两个相同的子序列(通过print我的意思是颜色).此外,这两个子序列的索引集合的联合必须是一组连续的自然数(整数的整数).

在数学中,我正在寻找的东西被称为"紧身双胞胎",如果它有帮助的话.(例如,请参阅此处的文件(PDF).)

我举几个例子:

1)考虑字符串231213231

它有两个子序列,我正在寻找"123"的形式.要看到它更好看这个图像:

第一个子序列标有下划线,第二个子序列标有上划线.如你所见,他们拥有我需要的所有属性.

2)考虑字符串12341234

3)考虑字符串12132344.

现在它变得更加复杂:

4)考虑字符串:13412342

它也不是那么容易:

我认为这些例子很好地解释了我的意思.

我一直在思考一个可以做到这一点但却没有成功的算法.

为了着色,我想使用这段代码:

 using namespace std;
HANDLE  hConsole;
        hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, k);

其中k是颜色.

任何帮助,甚至提示,都将受到高度赞赏.

Answer 1

这是一个测试紧密双胞胎的简单递归。当存在重复项时，它会拆分决策树，以防重复项仍然是第一个双胞胎的一部分。您必须在每个偶数长度的子字符串上运行它。针对较长子字符串的其他优化可能包括字符计数的哈希测试，以及匹配候选双胞胎的非重复部分（在整个子字符串中仅出现两次的字符）。

函数说明：

首先，创建一个哈希，其中每个字符作为键，其出现的索引作为值。然后我们遍历哈希：如果字符数为奇数，则函数返回 false；如果字符数为奇数，则函数返回 false。并且计数大于 2 的字符索引被添加到重复项列表中 - 其中一半的字符属于一个双胞胎，但我们不知道是哪一个。

递归的基本规则是仅i当在字符串中稍后找到匹配项时才增加，同时保留必须跳过而不查找匹配项的所选匹配项 ( js)的记录。i它之所以有效，是因为如果我们按顺序找到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,j,js);

    // yet to find twin, no match
    } else if (s[i] != s[j]){
      return f(i,j + 1,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,j + 1,js) | f(i + 1,j + 1,_js);          

      // it's a twin
      } else {
        js.add(j);
        return f(i + 1,j + 1,js);
      }
    }
  }

  return f(0,1,new Set());
}

console.log(isTightTwins("1213213515")); //  true
console.log(isTightTwins("11222332")); // false