给定一个字符串，在其中找到两个连续索引的相同子序列 C++

Question

给定一个字符串，在其中找到两个连续索引的相同子序列 C++

c++algorithm

7

我需要构建一个算法（不一定有效），给定一个字符串，找到并打印出两个相同的子序列（打印指着色，例如）。此外，这两个子序列的索引集合的并集必须是连续自然数集合（整数的完整段）。

在数学上，我正在寻找的东西称为“紧密双胞胎”，如果有帮助的话。（例如，请参见此处的论文（PDF）。）

让我举几个例子：

1）考虑字符串231213231

它有两个我要找的形式为“123”的子序列。要更好地看到它，请查看此图像：

第一个子序列用下划线标记，第二个用上划线标记。你可以看到它们具备我需要的所有属性。

2）考虑字符串12341234。

3）考虑字符串12132344。

现在情况变得更加复杂：

4）考虑字符串：13412342

这也不是那么容易的：

我认为这些示例已经很好地解释了我的意思。

我已经想了很长时间，想要编写一个能够实现这一点的算法，但是没有成功。

对于着色，我想使用这段代码：

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

其中k代表颜色。

任何帮助，即使是提示，都将不胜感激。

- Mateusz

1

如果过期时间算法正确，任务就很容易。 - user31264

1

我投票支持重新开放，因为这个问题似乎很有趣。 - MBo

1

我不认为将这个问题作为过于广泛而被暂停是合理的。提问者要求一个满足明确定义需求的算法。如果允许人们提出满足该需求的算法，并比较各种算法的复杂性，Stack Overflow将会受益。提问者对exptime算法感到满意并不影响这一点。事实上，我相信可以通过模拟一组NFAs在多项式时间内满足它，其中每个NFA都有一个状态，给出了分配给每个序列的字符数。 - mcdowella

1

@j_random_hacker：不，我希望一找到紧密的双子就停下来。比如，如果我有一个字符串：1231123123，我可以在找到“11”的时候停止。 - Mateusz

1

@VedangMehta：我认为你误解了问题。我再换一种方式来解释一下：将长度为n的字符串视为一个数学函数f，将范围在1…n之间的整数i映射到一个字符上。我们正在寻找两组整数A和B，使得满足以下条件：（1）A和B是不相交的；（2）A和B的并集是某个整数区间(i，j)，其中1 <= i <= j <= n（即没有“间隙”）；（3）如果我们按递增顺序列出A中的整数并对每个整数应用f，则我们得到的(j-i+1)个字符的字符串等于我们使用B进行相同操作时得到的字符串。 - j_random_hacker

显示剩余11条评论

4个回答

2

警告：评论者גלעד ברקן指出，这个算法对于字符串1213213515给出了错误的答案6（比应该可能的答案还要高！）。我的实现得到了相同的错误答案，因此似乎存在着这个算法的严重问题。在我找到问题所在之前，请不要相信这个算法！

我想到了一种解决方案，可以在O(n^3)时间和O(n^2)空间内完成，适用于长度不超过1000的字符串。它基于对最长公共子序列（LCS）的通常概念进行微调。为简单起见，我将描述如何在输入字符串中以位置1开始查找具有“紧密双生”属性的最小长度子串，假设输入字符串的长度为2n；每次在输入字符串中的下一个位置上运行此算法2n次。

“自避免”的公共子序列

如果长度为2n的输入字符串S具有“紧密双生”（TT）属性，则它与自身具有公共子序列（或等效地说，两个S的副本具有公共子序列），该公共子序列：

长度为n，并且
遵守以下附加约束条件：第一个S的任何字符位置都不能与第二个副本中的相同字符位置匹配。

实际上，我们可以安全地将后者的约束条件缩紧为第一个S的任何字符位置都不会与第二个副本中的等于或更低字符位置匹配，因为我们将按照长度递增的顺序查找TT子串，并且（如下面部分所示）在任何最小长度TT子串中，都可以将字符分配给两个子序列A和B，使得对于任何匹配的字符对（i，j），其中i < j是子串中的位置，位于位置i的字符被分配给A。称这样的公共子序列为自避免公共子序列（SACS）。

使有效计算成为可能的关键在于，长度为2n的字符串没有任何SACS能够具有超过n个字符（显然你无法将超过2组n个字符塞入长度为2n的字符串中），因此如果这样的长度为n的SACS存在，则必须是最大可能长度。 因此，要确定S是否为TT，只需在S和其自身之间查找最大长度的SACS，并检查其实际长度是否为n。

动态规划计算

我们定义f(i, j)为S的长度为i的前缀和S的长度为j的前缀的最长自避不同子序列的长度。要计算f(i, j)，我们可以使用通常LCS动态规划公式的一个小修改：

f(0, _) = 0
f(_, 0) = 0
f(i>0, j>0) = max(f(i-1, j), f(i, j-1), m(i, j))
m(i, j) = (if S[i] == S[j] && i < j then 1 else 0) + f(i-1, j-1)

如您所见，唯一的区别是增加了条件&& i < j。与通常的LCS DP一样，计算它需要O(n^2)的时间，因为两个参数都在0到n之间，而递归步骤外所需的计算是O(1)。(实际上，我们只需要计算这个DP矩阵的“上三角”，因为对角线以下的每个单元格(i, j)都将被相应的单元格(j, i)支配，尽管这不会改变渐近复杂度。)

要确定字符串的长度为2j的前缀是否为TT，我们需要在所有0 <= i <= 2n的情况下找到f(i, 2j)的最大值，即DP矩阵第2j列中的最大值。通过记录迄今为止看到的最大值并根据需要更新每个DP单元格中的最大值，可以在O(1)的时间内计算每个DP单元格的最大值。从j = 1到j = 2n的递增顺序让我们逐列填充DP矩阵，总是先处理S的较短前缀，然后再处理较长前缀，因此在处理第2j列时，我们可以安全地假设没有更短的前缀是TT(因为如果有的话，我们早就发现了它并且已经终止了)。

- j_random_hacker

非常感谢，但是您能告诉我如何从您的算法（如果我没记错的话，它只是确定字符串是否有紧密孪生）转换为实际打印紧密孪生的算法吗？我知道我可能听起来很傻，但我只是一个编程初学者。 - Mateusz

1

使用您提供的函数（字符串索引从0开始，我假设是这样的？），我得到了不同的结果，对于这个字符串“1213213515”（5），和这个字符串“1213243545”（4）。如果字符串索引从1开始，该函数分别产生6和5。请注意，第一个字符串包含一个重复的1，而不是每个双子中的4。我们可以假设结果超过字符串长度一半总是有效的，只是意味着有重复吗？ - גלעד ברקן

1

@Mateusz 和 j_random_hacker，这里有一些字符串，对于这个答案中的函数似乎会返回错误的结果。其中一个字符串中，某些字符出现了奇数次；而在另一个字符串中，字符计数是偶数： "1213213525" 和 "1213215351"。 - גלעד ברקן

@גלעדברקן：感谢您的评论。我现在已经在C++中实现了DP，链接在这里：http://ideone.com/I4CiJy，我得到了与您在第一条评论中相同的答案（我假设字符串是从1开始计数的）——这非常强烈地表明我的算法存在根本性的问题:( 我会发布警告并进一步调查... - j_random_hacker

我添加了一个简单的递归，但如果双胞胎中都包含重复项，我不确定能做多少。我认为当没有重复项时，LCS 应该可以工作，但我并不完全确定。 - גלעד ברקן

1

我希望将此问题视为动态规划/模式匹配问题。我们逐个字符从左到右处理，并维护一群非确定有限自动机（Non-Deterministic Finite Automata / NDFA），这些自动机对应于部分匹配。我们从单个空匹配开始，每个字符都会扩展每个NDFA的所有可能方式，每个NDFA可能产生许多子级，然后去重结果-因此我们需要最小化保持在NDFA中的状态以限制群体的大小。

我认为NDFA需要记住以下内容：

1）它跳过了匹配区域之前的k个字符。

2）一个后缀，它是一个p字符字符串，表示尚未匹配需要通过上划线进行匹配的字符。

我认为您总是可以假设p字符字符串需要与上划线匹配，因为如果您在整个答案中交换上下划线，则始终可以交换上下划线。

当您看到新字符时，可以通过以下方式扩展NDFAs：

a）只有跳过的NDFA可以添加跳过。

b）NDFA始终可以将新字符添加到其后缀中，后缀可能为空

c) 一个带有字符 p 的 NDFA，如果其第一个字符与新字符匹配，则可以变成一个带有 p-1 字符串的 NDFA，该字符串由旧后缀的最后 p-1 个字符组成。如果该字符串现在为零长度，则已找到匹配项，并且如果您将每个 NDFA 与其父级保持链接，则可以计算出它是什么。

我原以为我可以使用更简洁的编码方式来保证只有多项式的牛群大小，但我无法使其工作，并且我无法证明这里有多项式行为，但我注意到某些退化行为的情况被合理处理，因为它们导致了到达相同后缀的多种方式。

- mcdowella

1

假设字符串长度为N。

有两种方法。

方法1。这种方法总是指数级时间复杂度。

对于每个可能的长度为1..N/2的子序列，列出该子序列的所有出现次数。对于每个出现次数，列出所有字符的位置。

例如，对于123123，应该是：

(1, ((1), (4)))
(2, ((2), (5)))
(3, ((3), (6)))
(12, ((1,2), (4,5)))
(13, ((1,3), (4,6)))
(23, ((2,3), (5,6)))
(123, ((1,2,3),(4,5,6)))
(231, ((2,3,4)))
(312, ((3,4,5)))

后两种方法并不必要，因为它们只出现一次。

一种方法是从长度为1（即字符）的子序列开始，然后继续到长度为2的子序列等。在每个步骤中，删除所有仅出现一次的子序列，因为您不需要它们。

另一种方法是检查所有长度为N的2 ** N个二进制字符串。每当二进制字符串没有超过N / 2个“1”数字时，请将其添加到表中。最后删除所有仅出现一次的子序列。

现在，您拥有一个出现多次的子序列列表。对于每个子序列，检查所有成对物品，并检查这样的成对物品是否形成紧密的孪生。

方法2.直接寻找紧密的孪生。对于每个N *（N-1）/ 2个子字符串，请检查子字符串是否为偶数长度，并且每个字符都出现偶数次，然后，作为其长度L，请检查它是否包含两个长度为L / 2的紧密孪生。有2 ** L种分割它的方式，您可以简单地检查它们全部。还有更有趣的寻找t.t.的方法。

- user31264

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

这是一个简单的递归函数，用于测试紧密双子。当出现重复时，如果重复仍然是第一对双子的一部分，则会将决策树拆分。您需要在每个偶数长度的子字符串上运行它。针对更长的子字符串的其他优化可能包括哈希测试字符计数，以及匹配候选双子的非重复部分（只在整个子字符串中出现两次的字符）。

该函数的解释：

首先，使用每个字符作为键和其出现的索引作为值创建哈希表。然后我们遍历哈希表：如果字符计数为奇数，则函数返回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