文档章节

给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串

一贱书生
 一贱书生
发布于 2016/11/28 15:08
字数 1086
阅读 59
收藏 0

给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串。

解答

字符串的多模式匹配问题。

我们把S称为目标串,T中的字符串称为模式串。设目标串S的长度为m,模式串的平均长度为 n,共有k个模式串。如果我们用KMP算法(或BM算法)去处理每个模式串, 判断模式串是否在目标串中出现, 匹配一个模式串和目标串的时间为O(m+n),所以总时间复杂度为:O(k(m+n))。 一般实际应用中,目标串往往是一段文本,一篇文章,甚至是一个基因库, 而模式串则是一些较短的字符串,也就是m一般要远大于n。 这时候如果我们要匹配的模式串非常多(即k非常大),那么我们使用上述算法就会非常慢。 这也是为什么KMP或BM一般只用于单模式匹配,而不用于多模式匹配。

那么有哪些算法可以解决多模式匹配问题呢?貌似还挺多的,Trie树,AC自动机,WM算法, 后缀树等等。我们先从简单的Trie树入手来解决这个问题。

Trie树,又称为字典树,单词查找树或前缀树,是一种用于快速检索的多叉树结构。 比如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。

Trie树可以利用字符串的公共前缀来节约存储空间,这也是为什么它被叫前缀树。

如果我们有以下单词:abc, abcd, abd, b, bcd, efg, hig, 可以构造如下Trie树: (最右边的最后一条边少了一个字母)

 

回到我们的题目,现在要在字符串S中查找T中的字符串是否出现(或查找它们出现的位置), 这要怎么和Trie扯上关系呢?

假设字符串S = “abcd",那么它的所有后缀是:

abcd
bcd
cd
d

我们发现,如果一个串t是S的子串,那么t一定是S某个后缀的前缀。比如t = bc, 那么它是后缀bcd的前缀;又比如说t = c,那么它是后缀cd的前缀。

因此,我们只需要将字符串S的所有后缀构成一棵Trie树(后缀Trie), 然后查询模式串是否在该Trie树中出现即可。如果模式串t的长度为n, 那么我们从根结点向下匹配,可以用O(n)的时间得出t是否为S的子串。

下图是BANANAS的后缀Trie:

 

后缀Trie的查找效率很优秀,如果你要查找一个长度为n的字符串,只需要O(n)的时间, 比较次数就是字符串的长度,相当给力。 但是,构造字符串S的后缀Trie却需要O(m2 )的时间, (m为S的长度),及O(m2 )的空间。

 

 

在CODE上查看代码片派生到我的代码片

  1. package Hard;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.HashMap;  
  5.   
  6.   
  7. /** 
  8.  * Given a string s and an array of smaller strings T, design a method to search s for each small string in T. 
  9.  
  10. 译文: 
  11.  
  12. 给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串。 
  13.  * 
  14.  */  
  15. public class S18_8 {  
  16.   
  17.     // 后缀树节点  
  18.     static class SuffixTreeNode {  
  19.         HashMap<Character, SuffixTreeNode> children = new HashMap<Character, SuffixTreeNode>();  
  20.   
  21.         char value;  
  22.         ArrayList<Integer> indexes = new ArrayList<Integer>();  
  23.   
  24.         public SuffixTreeNode() {  
  25.         }  
  26.   
  27.         public void insertString(String s, int index) {  
  28.             indexes.add(index);  
  29.             if (s != null && s.length() > 0) {  
  30.                 value = s.charAt(0);  
  31.                 SuffixTreeNode child = null;  
  32.                 if (children.containsKey(value)) {  
  33.                     child = children.get(value);  
  34.                 } else {  
  35.                     child = new SuffixTreeNode();  
  36.                     children.put(value, child);  
  37.                 }  
  38.                 String remainder = s.substring(1);  
  39.                 child.insertString(remainder, index);  
  40.             }  
  41.         }  
  42.   
  43.         public ArrayList<Integer> search(String s) {  
  44.             if (s == null || s.length() == 0) {  
  45.                 return indexes;  
  46.             } else {  
  47.                 char first = s.charAt(0);  
  48.                 if (children.containsKey(first)) {  
  49.                     String remainder = s.substring(1);  
  50.                     return children.get(first).search(remainder);  
  51.                 }  
  52.             }  
  53.             return null;  
  54.         }  
  55.     }  
  56.   
  57.     // 后缀树  
  58.     static class SuffixTree {  
  59.         SuffixTreeNode root = new SuffixTreeNode();  
  60.   
  61.         public SuffixTree(String s) {  
  62.             for (int i = 0; i < s.length(); i++) {  
  63.                 String suffix = s.substring(i);  
  64.                 root.insertString(suffix, i);  
  65.             }  
  66.         }  
  67.   
  68.         public ArrayList<Integer> search(String s) {  
  69.             return root.search(s);  
  70.         }  
  71.     }  
  72.   
  73.     public static void main(String[] args) {  
  74.         String testString = "mississippi";  
  75.         String[] stringList = { "is", "sip", "hi", "sis" };  
  76.         SuffixTree tree = new SuffixTree(testString);  
  77.         for (String s : stringList) {  
  78.             ArrayList<Integer> list = tree.search(s);  
  79.             if (list != null) {  
  80.                 System.out.println(s + ": " + list.toString());  
  81.             }  
  82.         }  
  83.     }  
  84.   
  85. }  

© 著作权归作者所有

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
KMP算法初探

[edit by xingoo] kmp算法其实就是一种改进的字符串匹配算法。复杂度可以达到O(n+m),n是参考字符串长度,m是匹配字符串长度。 传统的算法,就是匹配字符串与参考字符串挨个比较,如果相同就...

青夜之衫
2017/12/05
0
0
KMP算法的理解,伪代码,c代码实现

1、字符串问题形式化定义:假设文本是一个长度为n的T[1..n],而模式是一个长度为m的数组P[1..m],其中m<=n,如果有T[s+1..s+m]==P[1..m],那么就称模式P在T中出现。s为有效偏移,否则称为无效...

thoresa
2015/05/18
0
0
LeetCode算法题-Isomorphic Strings(Java实现)

这是悦乐书的第191次更新,第194篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第50题(顺位题号是205)。给定两个字符串s和t,确定它们是否是同构的。如果s中的字符可以替换...

小川94
2018/12/04
0
0
awk 字符串函数

awk 提供了许多强大的字符串函数,见下表: awk 内置字符串函数 gsub(r,s) 在整个 $0 中用 s 替代 r gsub(r,s,t) 在整个 t 中用 s 替代 r index(s,t) 返回 s 中字符串 t 的第一位置 length(s...

云栖希望。
2017/12/04
0
0
LeetCode算法题-Valid Anagram(Java实现)

这是悦乐书的第198次更新,第205篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第61题(顺位题号是242)。给定两个字符串s和t,写一个函数来确定t是否是s的anagram。例如: ...

小川94
2018/12/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

硬件配置

https://akkadia.org/drepper/futex.pdf sudo lshw -businfo[sudo] lambda 的密码: Bus info Device Class Description======================================......

MtrS
今天
2
0
springmvc的return “success”源码解读

qqqq

architect刘源源
今天
5
0
Java程序员五面阿里分享 逆袭成功 太不容易了!

前言 拿到阿里实习offer,经历了5次面试,其中4轮技术面,1轮HR面试。在这里分享一下自己的面试经验和学习心得。希望能够帮助更多的小伙伴。 我本科毕业于中南大学信管专业,真正开始学习Jav...

别打我会飞
昨天
4
0
Android Camera模块解析之视频录制

《Android Camera架构》 《Android Camera进程间通信类总结》 《Android Camera模块解析之拍照》 《Android Camera模块解析之视频录制》 《Android Camera原理之CameraDeviceCallbacks回调模...

天王盖地虎626
昨天
2
0
手把手教你使用issue作为博客评论系统

自从上周在阮一峰的 每周分享第 60 期 看到了可以将 GitHub 的 issue 当作评论系统,插入第三方网页的 JS 库——utterances。我就对此“魂牵梦绕”。个人博客使用的是VuePress。 TLDR (不多废...

jump--jump
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部