字串- DP

Question

我有一个字串，我必须确定最长的子串，这样一个单词的最近两个字母必须是一个单词后面的前两个字母。

例如，关于以下几个字：

st artifact，ar，ctenophore，list，reply

编辑:所以最长的子字符串应该是star， reply。

我正在寻找一个在O(n)中解决这个问题的想法。没有代码，我很感激关于如何解决它的任何建议。

Answer 1

首先，把所有单词读成一个结构。)你不需要这样做，但那样做更容易。你也可以一边读一边读。)

其思想是有一个查找表(例如Dictionary中的.NET)，它将包含键值对，这样每个单词的最后两个字母都会在这个查找表中有一个条目，它们的对应值将永远是迄今为止找到的最长的‘子字符串’。

时间复杂性是O(n) --您只需要遍历列表一次。

逻辑：

maxWord <- ""
word <- read next word
initial <- get first two letters of word
end <- get last two letters of word

if lookup contains key initial //that is the longest string so far... add to it
    newWord <- lookup [initial] value + ", " + word
    if lookup doesn't contain key end //nothing ends with these two letters so far
        lookup add (end, newWord) pair
    else if lookup [end] value length < newWord length //if this will be the longest string ending in these two letters, we replace the previous one
        lookup [end] <- newWord
    if maxWord length < newWord length //put this code here so you don't have to run through the lookup table again and find it when you finish
        maxWord <- newWord
else //lookup doesn't contain initial, we use only the word, and similar to above, check if it's the longest that ends with these two letters
    if lookup doesn't contain key end
        lookup add (end, word) pair
    else if lookup [end] value length < word length
        lookup [end] <- word
    if maxWord length < word length
        maxWord <- word

maxWord变量将包含最长的字符串。

以下是C#中的实际工作代码，如果需要的话：http://pastebin.com/7wzdW9Es

Answer 2

与O(n)最接近的是：

你应该用身份证标记每个单词。以你的例子为例：

star => 1子串可能。因为你在寻找最长的子串，如果一个子串与ar一起出现，那么它不是最长的，因为你可以在前面添加星星。让我们将星号ID设置为1，其字符串比较是ar

artifact =>第一个字符匹配第一个可能的子字符串。让我们将工件ID设置为1，并将字符串比较更改为ct

book =>第一个字符在字符串比较中不匹配任何内容(只有ct )，因此我们将图书ID设置为2，并添加了一个新的字符串比较：ok

..。

list =>前两个字符与字符串比较中的任何内容不匹配( ID == 1中的re和ID ==2中的ok )，因此我们创建了另一个ID =3和另一个字符串比较

最后，您只需要查看ID，看看哪一个元素最多。你也可以一边数一边数。

这个算法的主要思想是记住我们正在寻找的每个子字符串。如果找到匹配项，只需使用两个新的最后字符更新正确的子字符串，如果不更新，则将其添加到“内存列表”中。

重复此过程使其成为O(n*m)，m表示不同ID的数量。