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

2018-08-30 18:00:08 +08:00
 Nirlan

RT.

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

和

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

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

请各位大佬给个思路.

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

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

https://www.v2ex.com/t/484671

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

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

© 2021 V2EX