字符串匹配算法

字符串匹配：在字符串中查找子串，或者查找符合某种模式的字符组合。

字符串匹配的算法有：

字符串T为主串，P为需要匹配的模式或者固定的字符串，T与P的长度分别为n,m,即字符数组的T的下标是0-n-1,P的下标是0-m-1, 

  1. 蛮力法

  2. Rabin-Karp字符串匹配算法

  3. 采用有限状态机实现的字符串匹配算法

  4. KMP算法

  5. Boyer-Moore算法

  6. 后缀树

1.蛮力法

蛮力法（brute force method，也称为穷举法或枚举法）是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。但是，用蛮力法设计的算法时间特性往往也是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的 [1]  。---来自百度词条

判断T中是否有可以匹配的字符串,该算法逐个匹配T中可能出现模式P的那些位置，由于T的长度为n,故只需考虑n-m-1个位置即可，不用考虑T中之后的元素，因为后面的位置无法容纳长度为m的子串。

	public boolean method(int [] T, int n,int [] P,int m) {
		for(int i = 0; i< n- m +1 ; i++) {
			int j = 0;
			while(j < m &&  P[j] == T[i+j])
				j= j+1;
			if(j == m - 1) 
				return true;	
		}
		return false;
	}

2. Rabin-Karp字符串匹配算法

采用哈希技术实现，即先计算T的前m个元素的hash值，然后和P的hash值进行比较，如果相同，则匹配成功，如果没有，则继续从T中选取下一个m个元素，计算其hash值，进行比较，直到到达T的 n-m + 1 个元素

如果发生冲突，则还需要进行比较，重要的是hash函数的选择。

3.有限状态机来实现字符串匹配算法

https://blog.csdn.net/tyler_download/article/details/52549315

4.KMP算法

由Knuth,Morris,Pratt提出，可以在O(n)级别的时间内判断T与P是否匹配，需要用到一张表，通常称为前缀函数，前缀表，或失配函数，记作F,使用这张表，算法可以不想退回去考虑T里面那些已经判断过的字符。

public int [] Prefix_Table(int [] P,int m) {
		int [] F = new int [m-1];
		int i = 1,j = 0;F[0] = 0;
		while(i<m) {
			if(P[i] == P[j]) {
				F[i] = j + 1;
				i++;
				j++;
			}else if( j > 0)
				j = F[j-1];
			else {
				F[i] = 0;
				i++;
			}
		}
		return F;
	}
	public int KMP(int [] T,int n,int [] P,int m) {
		int i =0 ,j = 0;
		int [] F = Prefix_Table(P, m);
		while(i < n) {
			if(T[i] == P[j]) {
				if(j == m-1)
					return i-j;
				else {
					i++;
					j++;
				}
			}else if(j> 0)
				j = F[j-1];
			else
				i++;
		}
		return -1;	
	}

5.Boyce_Moore算法

待定

6.后缀树

保存字符串的数据结构有：

哈希：哈希表存放整数或字符串，以字符串为键。但是无法保存顺序信息，无法知道hash函数究竟会把原数据映射到哪里，这将导致某些查找任务需要耗时更长，因为hash函数的计算是根据字符串整个键来确定存储位置，我们无法通过一个字符，即A开头，来进行查找。

二叉搜索树：按照字符顺序来存放字符串。每访问一个节点，有可能要将待查找的字符串与该节点的数据完全对比一次，增加查找操作的时间。

前缀树：每个节点都含有一些指针，，分别对应于字母表中的各个字母。

前缀树的节点结构为：（例如英语字母表由26个字母组成）

	class TrieNode{
		char data;
		int is_End_Of_String;
		TrieNode[] child = new TrieNode[26];
	}

	//判断是否有与之对应的子节点
	public TrieNode subNode(TrieNode root,char c) {
		if(root != null) {
			for(int i=0;i<26;i++) {
				TrieNode child = root.child[i];
				if(child.data == c)
					return child;
			}
		}
		return null;
	}
插入//查找。。。

三元树： 

由Jon Bentley 及 Sedgewick给出，结合二叉树和前缀树的优点。

三元树的声明:

	class TSTNode{
		char data;
		int is_End_Of_String;
		TSTNode left;//left所指向的节点用来表示在字母表上面小于data的所有字符串
		TSTNode eq;//eq所指向的节点用来表示在字母表上面等于data的所有字符串
		TSTNode right;//right所指向的节点用来表示在字母表上面大于data的所有字符串
	}

后缀树：用来存放字符串的数据结构，可迅速完成查询任务，建树麻烦，但是可在线性时间内完成很多字符串的操作。

前缀：字符串T=T1 T2 ...Tn, 则T1 ...Ti就是T的前缀，i可取1-n之间的任意整数，

后缀：字符串T= T1 T2...Tn ，则Ti...Tn就是T的后缀，i可取n-1之前的任意数。

如果匹配成功，则有：T的某个后缀，使得P是该后缀的前缀  或T的某个前缀，使得P是该前缀的后缀。

后缀树的条件：

⑴含有n个节点，节点的编号从1至n的整数来编号

⑵除了根节点之外，每个内部节点，至少有两个子节点

⑶每条边都与T中某个非空的子字符串相关联

⑷有同一个节点发出的那些边，其所关联的子字符串均已不同的字母开头。

⑸从根节点到每一个叶节点之间的路径，均表示字符串T的某一种后缀。n条路径覆盖所有T的后缀。

树构建过程：

⑴把字符串T的所有后缀放入集合S中，并给每一种后缀添加$符号

⑵根据首字符来给$中的这些后缀排序

⑶按照首字母的不同来划分为不同的组。

①如果改组只有一个元素，就创建对应的叶节点

②否则，就把各元素所共同拥有的最长前缀找出来，并创建内部节点，然后把这个前缀从各组的元素中分别拿掉，并递归执行第2，3步。

 

 

 

内容参考《程序员面试手册》