算上仙境

Question

该文本爱丽丝梦游仙境包含单词"仙境"的8倍.(让我们对这个问题不区分大小写).

但是,如果计算非连续子序列以及子串,它会包含多次该词,例如.

要么井很深,要么她的速度非常慢,因为她有足够的时间去看她和WONDER接下来会发生什么.首先,她试图大号 OOK下来和做什么,她要来,但天太黑什么都看不到;

(子序列是可以通过删除一些元素而不改变其余元素的顺序从另一个序列导出的序列.-Wikipedia)

这本书包含仙境这个词作为一个子序列多少次？我希望这将是一个很大的数字 - 这是一本很长的书,有许多w和o,n和d.

我尝试了强力计数(递归使得循环10深)但它太慢了,即使对于那个示例段落也是如此.

Answer 1

假设您不想搜索wonderland,但只是为了w.然后你只需计算w故事发生的次数.

现在让我们说你想要的wo.对于您找到的当前模式的每个第一个字符,您可以添加到计数中:

1. 在故事的其余部分中出现没有第一个字符的当前模式的次数,在此字符之后:所以你已将问题减少(story[1..n], pattern[1..n])到(story[2..n], pattern[2..n])

2. 在故事的其余部分中,整个当前模式发生了多少次.所以你已经把问题减少了(story[2..n], pattern[1..n])

现在你可以添加两个.如果我们谈论子问题,就没有过度计算.考虑这个例子wawo.显然,wo发生的2时间.您可能会认为计数会像:

1. 对于第一个w,添加1因为o在它之后发生一次,而另一个1因为wo在它之后发生一次.

2. 对于第二个w,添加1因为o在它之后发生一次.

3. 答案是3,这是错误的.

但这是实际发生的事情:

(wawo, wo) -> (awo, o) -> (wo, o) -> (o, o) -> (-, -) -> 1
                                            -> (-, o) -> 0
           -> (awo, wo) -> (wo, wo) -> (o, wo) -> (-, wo) -> 0
                                    -> (o, o) -> (-, -) -> 1
                                              -> (-, o) -> 0

所以你可以看到答案是2.

如果找不到a w,则此位置的计数是wo在当前字符之后发生的次数.

这允许使用memoization进行动态编程:

count(story_index, pattern_index, dp):
  if dp[story_index, pattern_index] not computed:
    if pattern_index == len(pattern):
      return 1
    if story_index == len(story):
      return 0

    if story[story_index] == pattern[pattern_index]:
      dp[story_index, pattern_index] = count(story_index + 1, pattern_index + 1, dp) + 
                                       count(story_index + 1, pattern_index, dp) 
    else:
      dp[story_index, pattern_index] = count(story_index + 1, pattern_index, dp)

  return dp[story_index, pattern_index]

打电话给count(0, 0, dp).请注意,您可以使代码更清晰(删除重复的函数调用).

Python代码,没有任何记忆:

def count(story, pattern):
  if len(pattern) == 0:
    return 1
  if len(story) == 0:
    return 0

  s = count(story[1:], pattern)
  if story[0] == pattern[0]:
    s += count(story[1:], pattern[1:])

  return s

print(count('wonderlandwonderland', 'wonderland'))

输出:

17

这是有道理的:对于故事i的第一个wonderland中的每个第一个字符,您可以将其与第二个中的剩余最终字符分组wonderland,为您提供10解决方案.另一个2是自己的话.其他五个是:

wonderlandwonderland
*********    *
********    **
********    *      *
**      **    ******
***      *    ****** 

你是对的,这将是一个巨大的数字.我建议您使用大整数或以模数结果.

9624您的示例段落将返回相同的程序.

Answer 2

字符串“wonderland”作为子序列在Alice in Wonderland ^1中出现 24100772180603281661684131458232 次。

主要思想是逐个字符地扫描主文本，对目标字符串的每个前缀（即：在本例中为“w”、“wo”、“won”、...、“ Wonderlan”和“wonderland”）截至目前这封信已出现。这些运行计数很容易计算和更新。如果当前字母没有出现在“wonderland”中，则计数保持不变。如果当前字母是“a”，那么我们将看到的“wonderla”的计数增加到到目前为止看到的“wonderl”的数量。如果当前字母是“n”，那么我们将“won”的计数增加“wo”的计数，将“wonderlan”的计数增加“wonderla”的计数。等等。当我们到达文本末尾时，我们将根据需要计算“wonderland”的所有前缀的计数，包括字符串“wonderland”本身。

这种方法的优点是它需要单次遍历文本并且不需要 O(n) 递归调用（这可能会超过最大递归深度，除非您采取一些聪明的措施）。

代码

import fileinput
import string

target = 'wonderland'

prefixes = dict()
count = dict()

for i in range(len(target)) :
    letter = target[i]
    prefix = target[:i+1]
    if letter not in prefixes :
        prefixes[letter] = [prefix]
    else :
        prefixes[letter].append(prefix)
    count[prefix] = 0L

for line in fileinput.input() :
    for letter in line.lower() :
        if letter in prefixes :
            for prefix in prefixes[letter] :
                if len(prefix) > 1 :
                    count[prefix] = count[prefix] + count[prefix[:len(prefix)-1]]
                else:
                    count[prefix] = count[prefix] + 1

print count[target]

1. 使用古腾堡计划中的文本，以“第一章：掉进兔子洞”开始，以“THE END”结束