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

Question

我需要构建一个算法(不一定有效)，给定一个字符串查找并打印两个相同的子序列(例如打印我指的是颜色)。而且，这两个子序列的索引集的并集必须是一组连续的自然数(整段整数)。

在数学中，我正在寻找的东西叫做“紧双胞胎”，如果它有帮助的话。 (例如，参见 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 是颜色。

我们将不胜感激任何帮助，甚至是提示。

Answer 1

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

函数说明:

首先，创建一个散列，每个字符作为键，它出现的索引作为值。然后我们遍历散列:如果字符数是奇数，函数返回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