给出两份文件:
现在是我们不满的冬天,这是由约克的太阳创造的灿烂的夏天;所有的云彩在我们的房子里,在深深的海洋的怀抱中被掩埋。现在,我们的眉毛被胜利的花环捆住了;我们被瘀伤的手臂挂在纪念碑上;我们的严厉通知变成了欢快的会议;我们可怕的游行变成了令人愉快的措施。
(理查三世)
理查德(约克公爵):把他的酒杯三次敲在桌子上,安静!安静!为了国王! 国王(理查德三世):站着,驼背,现在尴尬地说着,是我们甜蜜内容的夏天,由这些都铎云铸成的冬天。
(BlackAdder,第一季,第1集)
谁能用哪种算法来找出两个文档中都存在哪一个三字序列?当然,如果有的话--这是不确定的。
在本例中,"now is the“是两个文档中唯一出现的3字序列。
发布于 2010-11-26 15:42:35
如果没有蛮力,最简单的解决方案是创建一个散列图,其中包含一个文本的每个元组的条目,然后检查另一个文本中的每个元组是否存在于散列图中。这将是线性的,给定一个恒定的窗口(3字),但是我们可以在线性时间内做到这一点,而与窗口大小无关。
为了有效地完成这个任务,我们使用了一个滚动散列。滚动散列的输入字符将是单词的散列。这种技术被称为Rabin-Karp算法。
发布于 2010-11-25 14:55:07
听起来你在寻找长度为3的普通子串,除了你的“字符串”是由单词组成的“字符”,而不是单个字符。所以,“我有一个狡猾的计划”是一串长度5。
后缀树通常在这里被提到:树,但是您是否需要这一点取决于您的文本的长度。两个嵌套循环来比较,从每对单词边界开始(每个字符串一个),最终将完成任务。
https://stackoverflow.com/questions/4278279
复制相似问题