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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2606 天前的主题，其中的信息可能已经有所发展或是发生改变。

RT.

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

和

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

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

请各位大佬给个思路.

字符

算法

子字符串

串数组

15 条回复 2018-09-03 15:16:47 +08:00

catinred

2018-08-30 18:02:11 +08:00

快要交暑假作业了吧？

Nirlan

2018-08-30 18:03:02 +08:00

@catinred #1 额...并不是...

orcusfox

2018-08-30 18:12:51 +08:00 via iPhone

没必要，全遍历一遍也就 O(n)，优化有啥意思？要一个词出现，用 kmp。要都出现，用 BitSet 建过滤器。

rrfeng

2018-08-30 18:13:30 +08:00 via Android

5000 字要什么性能？

iblislsy

2018-08-30 18:14:44 +08:00

@catinred 萧峰，小跳，葵花三式

Nirlan

2018-08-30 18:18:19 +08:00 via Android

@rrfeng 哦，像这样的 content 有几百万个

GtDzx

2018-08-30 18:21:37 +08:00

有个叫 AC 自动机的东西，你可以搜一下看看

Nirlan

2018-08-30 18:22:11 +08:00 via Android

@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 via iPhone

AC 自动机

crayygy

2018-08-30 23:06:48 +08:00 via iPhone

曾经用 AC 解决了一个性能问题，研究一下还是不错的

vjnjc

2018-08-30 23:52:13 +08:00 via Android

感觉用 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 字节遍历岂不美哉