RT.
已知一个长字符串,比如说一篇 5000 字的文章 content ,就是说这个 content 比较长
和
一组子字符串数组 如 ["北京","上海","深圳"] 就是说 每个子字符串很短
现在想找一个时间和空间复杂度最低的算法,来判断每个子字符串是否在文章中出现过
请各位大佬给个思路.
This topic created in 2831 days ago, the information mentioned may be changed or developed.
 |
1
catinred Aug 30, 2018
快要交暑假作业了吧？
|
 |
3
orcusfox Aug 30, 2018 via iPhone
没必要，全遍历一遍也就 O(n)，优化有啥意思？要一个词出现，用 kmp。要都出现，用 BitSet 建过滤器。
|
 |
4
rrfeng Aug 30, 2018 via Android
5000 字要什么性能？
|
 |
7
GtDzx Aug 30, 2018
有个叫 AC 自动机的东西，你可以搜一下看看
|
 |
9
vizee Aug 30, 2018
关键词: 多模匹配, 字典树, 前缀树, AC 自动机, DFA, 考虑时间空间: 双数组 AC 自动机
|
 |
10
leriou Aug 30, 2018
DFA
|
 |
11
dongyx Aug 30, 2018 via iPhone
AC 自动机
|
 |
12
crayygy Aug 30, 2018 via iPhone
曾经用 AC 解决了一个性能问题，研究一下还是不错的
|
 |
13
vjnjc Aug 30, 2018 via Android
感觉用 hashmap(string, boolean)足矣。
要的还感觉不够的话用类似 bitset 的方式，想办法把 string 转 int/long，然后用 boolean 判断是否已经存在，因为你要所有字符是否出现都要存储没啥特别优秀的方法。 （外行人出点馊主意～ |
 |
14
ronglexie Aug 30, 2018
Trie 树
|
 |
15
brucewuio Sep 3, 2018
才 5000 字节遍历 岂不美哉
|
Select Language