有一个词库里面包含d个词,词的最大字符长度为m,判断一篇文章中是否包含有词库中的词,文章最大长度为n,判断是否即可。

 

 

我曾经面试被问到这个问题,我觉得我的想法还不错,效率应该是n*m,应用kmp的思想应该还可以提高,今天就把这个问题写一下。

 

方法一:

利用子串查找的方法,遍历每一个词,进行判断。子串查找有一个高效的算法kmp,回头补进来代码,今天先写我想到的办法。  kmp复杂度问 n+m, 那么整体复杂度为  d*(n+m)

 

 

方法二:

按字构造词库,简历hash树结构。比如:  中国,中华,中国人 ,政府 即为:

【算法系列-3】判断文章中是否包含词库中的词-保持愤怒

 

从根往下,即可存储所有的词,每一层使用hash映射,在结尾的字上打个标识,告诉这是一个完整词的结尾。从根部与文章第一个字匹配,匹配成功继续往下匹配。直到不成功,匹配的位置向后移动。

该算法复杂度为    m*n  与d无关。 是否可以向kmp一样跳跃式往后移动,我目前还不清楚。

下面看一下算法:

 

 

所以,这次kmp也慢了。

 

未来: 如果再提供一个信息,文章数量为k,是否也可以从文章做工作。再议。