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