江湖救急...一个字符串匹配的算法问题.

2018 年 8 月 30 日
 Nirlan

RT.

已知一个长字符串,比如说一篇 5000 字的文章 content ,就是说这个 content 比较长

和

一组子字符串数组 如 ["北京","上海","深圳"] 就是说 每个子字符串很短

现在想找一个时间和空间复杂度最低的算法,来判断每个子字符串是否在文章中出现过

请各位大佬给个思路.

4209 次点击
所在节点    Java
15 条回复
catinred
2018 年 8 月 30 日
快要交暑假作业了吧？
Nirlan
2018 年 8 月 30 日
@catinred #1 额...并不是...
orcusfox
2018 年 8 月 30 日
没必要，全遍历一遍也就 O(n)，优化有啥意思？要一个词出现，用 kmp。要都出现，用 BitSet 建过滤器。
rrfeng
2018 年 8 月 30 日
5000 字要什么性能？
iblislsy
2018 年 8 月 30 日
@catinred 萧峰，小跳，葵花三式
Nirlan
2018 年 8 月 30 日
@rrfeng 哦，像这样的 content 有几百万个
GtDzx
2018 年 8 月 30 日
有个叫 AC 自动机的东西，你可以搜一下看看
Nirlan
2018 年 8 月 30 日
@GtDzx 感谢，我看一下
vizee
2018 年 8 月 30 日
关键词: 多模匹配, 字典树, 前缀树, AC 自动机, DFA, 考虑时间空间: 双数组 AC 自动机
leriou
2018 年 8 月 30 日
DFA
dongyx
2018 年 8 月 30 日
AC 自动机
crayygy
2018 年 8 月 30 日
曾经用 AC 解决了一个性能问题，研究一下还是不错的
vjnjc
2018 年 8 月 30 日
感觉用 hashmap(string, boolean)足矣。
要的还感觉不够的话用类似 bitset 的方式，想办法把 string 转 int/long，然后用 boolean 判断是否已经存在，因为你要所有字符是否出现都要存储没啥特别优秀的方法。
（外行人出点馊主意～
ronglexie
2018 年 8 月 30 日
Trie 树
brucewuio
2018 年 9 月 3 日
才 5000 字节遍历 岂不美哉

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/484671

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX