1、串的定义
这里所说的串指的是字串，就是字符串，当然不是烧烤串。计算机的字串是用编码形式保存的，通常的ASCII码，Unicode编码，中文的GBK等等。对于一个字串，定义为s="a1a2a3....an"，相应的对于另一个字串t=b1b2b2b3....bm，当且仅当n=m，且a1=b1,a2=b2,a3=b3....,an=bm，则两串相等。同时，当满足如下条件时s<t：
- n< m ， 且a1=b1(i=1,2,3....n)；
- 有k<=min(m,n)，使ai=bi(i=1,2,3,4,5...k-1)，ak<bk;(这种情况会根据编码计算，可能不同语言有不同处理)
2、朴素的模式匹配算法
模式匹配最先能想到的就是在一片文章中找到指定的单词，如文本的检索，引申到单词的统计。我们最简单想到的就是将材料文本当做一个很长的串，然后用对应的单词去匹配，具体是按照单词的字符一个个匹配，如果匹配到，继续，直到单词尾部，这是最理想的情况，否则，单词首字符再去比较文本第二个字符，依次直到获得结果。归纳如下：
- 匹配到，检索词，文本串同时推进；
- 未匹配到，检索词再去执行1，从文本串上次匹配的下一个字符开始；
朴素模式匹配算法的时间复杂度为最好为，最差是
代码如下
c++
//不存在匹配，返回0，长度存在t[0],s[0]
//s 待匹配，t匹配字串
//t 不空
int index(String s, String t, int pos){
int i = pos;
int j = 1;
while( i <= s[0] && j <= t[0]){
if(s[i] == t[j]){
++i;
++j;
}else{
i = i - j + 2; //从下一个位置开始
j = 1; //回到首位比较
}
}
if( j > t[0]){
return i - t[0];
}else{
return 0;
}
}
java
public class StringPattern {
public static void main(String[] args) {
String s = "dsfandkfnadsognoadsngasfsdbvonasdobvnadsodfnasonfo3n2n";
String p = "";
System.out.println(index(s, p));
}
private static int index(String s, String p) {
if (s == null || p == null || "".equals(p)) {
return -1;
}
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j >= p.length()) {
return i - j;
}
return -1;
}
}
3、KMP模式匹配
KMP算法是D.E.Knuth、J.H.Morris以及V.R.Pratt的发明，可以避免重复遍历的算法，大大提高匹配效率。KMP有些难以理解，这种算法是典型的通过对客观规律的总结，来归纳出一个合理的算法，再通过编程实现和优化的结果。我们看到的只有分析过程和算法结果，并对这个结果加以运用。我尽量简洁的来表述这个算法，会对一些难点进行重点强调和解释。本文是KMP的初级介绍，后面会专门介绍KMP的优化方案。
3.1 KMP原理
首先看下朴素匹配可以优化的点。例如：在S=abcdefgab中匹配T=abcdex，朴素算法首先从a一直匹配到f-x,第6位。然后下次匹配再从T-a去匹配S-b，一直到T-a匹配S-c，一直到再匹配到S-f,T-a。重点：这里我们能够发现，字串T中，首字母a与他之后的字符都不相等，因此之后关于T-a和S中随后字符的比较没有必要进行，这是因为在第一次比较就知道S中往后的都是不等的。推理如下：
图示
KMP匹配1
由于我们得到这种经验，如果匹配的串T和目标串S有连续相同的元素，则跳过比较，且这种情况会导致T中j值的变化。所以对于另一种情况如
S=abcabaabca,T=abcabx，由于T=(ab)c(ab)x，这里第一次j=1，后面j直接为3，即比较到c的位置，j的取值表示了当期字符之前的串在串中的相似度，相似度越高，j越大。我们将T各个位置上j值的变化表示为一个next的数组保存，抽象成函数表示为：
保护视力
网友评论