一次查找字符串中所有不同的最长子字符串

问题描述 投票:-1回答:1

在Boyer-moore和KMP算法以及其他字符串匹配算法中,必须定义一个子字符串以进行搜索以获得满意的结果。我的问题->是否可以在不定义要查找的子字符串的情况下找到字符串中所有不同的最长子字符串?我的意思是有可能开发出一种算法,该算法可以将每个最长的子字符串本身分开?如果是应该怎么办?

[这里我应该提到后缀树,我知道它在需要查找最长的公共子序列和最长的重复子序列时会很有帮助。但是问题首先是所有特征一次导致一个可能的结果,但是我需要一次找到所有不同的最长子序列。我不知道是否可能,这就是为什么我要问这个问题。

例如:

[从类似这样的字符串“ ABABABDCF”通常,可以期望获得如下输出。

“” ABABABDCF“,“ ABABAB”,“ DCF”,和其他可能的子字符串。

但是我只需要列表中下面两个子字符串。

“” ABABAB“,“ DCF”

上面的例子是一个小字符串,但我正在寻找一个解决方案,该字符串包含一百万个字符。

编辑:--->

如果算法选择某个子字符串作为最长子序列,那么下一个选择就不能成为上一个选择的一部分。

在Boyer-moore和KMP算法以及其他字符串匹配算法中,必须定义一个子字符串以进行搜索以获得满意的结果。我的问题->有没有办法找到所有不同的最长...

c++ string-matching
1个回答
0
投票

这是我的代码。我知道这很长而且很模糊,因为我不是编程专家。我相信可以对这些代码进行更多压缩。但是,我可以从我的项目的代码中获得令人满意的结果,并且我已经在到目前为止对我最合适的其他字符串上对该代码进行了测试。 。谢谢您的前一个答复。

© www.soinside.com 2019 - 2024. All rights reserved.