一、应用串的基本操作函数
Index(S,T,pos) 定位操作。若主串S中存在与串T值雷同的字串，则返回它在主串S中第pos个字符之后第一次呈现的地位；否则函数值为0
在Java中，对应函数为 S.indexOf(String T)
二、BF模式匹配算法
别离用i和j示意主串S和字串T中以后正在比拟的字符地位。算法思维为：从主串S的第pos个字符起，与模式串的第一个字符进行比拟，若相等，则持续一一比拟后续字符；否则从主串的下一个字符起再从新和模式串的字符比拟。依此类推，直至模式串T中的每个字符顺次和主串S中的一个间断的字符序列相等，则称匹配胜利，函数返回值为和模式串T中的第一个字符相等的字符在主串S中的序号，否则成匹配不胜利，函数返回值为0。
在匹配胜利的状况下，思考以下两种极其状况。其中m为主串长度，n为模式串长度。
（1）最好状况下，每趟不胜利的匹配都产生在模式串的第一个字符与主串中相应字符的比拟。此时的工夫复杂度为O(m+n) 例如： S="aaaaaaaba" T="ba"
（2）最坏状况下，每趟不胜利的匹配都产生在模式串的最初一个字符与主串中相应字符的比拟。此时的工夫复杂度为O(m*n) 例如： S="aaaaaaab" T="aab"
图1展现了模式串T=“abcac”和主串的匹配过程（pos=1）
BF算法思路简略。但当匹配失败时，主串的指针i总是回溯到i-j+1地位，模式串的指针j总是复原到首字符地位j=1。因而，算法工夫复杂度高。
三、KMP算法
（以下剖析元素下标皆从1开始）
改良点：失配时，不需回溯i指针，而是利用曾经比拟过的信息，仅将模式串向右挪动到一个适合的地位，并从这个地位开始和主串进行比拟，这个适合的地位仅与字串自身的构造无关，而与主串无关。KMP算法的工夫复杂度为O(m+n)。
回顾图1的匹配过程，在第三趟匹配中，i=7、j=5时失配，于是又从i=4、j=1处从新开始比拟。然而，i=4和j=1、i=5和j=1、i=6和j=1这三次比拟都是不用进行的，因为从第三趟匹配的后果可知，主串中第4、5、6个字符是’b’,’c’,’a’，而字串中的第一个字符是‘a‘，因而它无须再和这三个字符进行比拟，仅需将子串向右滑动3个字符的地位持续进行i=7、j=2时的字符比拟即可。
关键在于明确的晓得每个时刻须要挪动的间隔。在此之前，引入三个概念：前缀、后缀和局部匹配值
- 前缀：除最初一个字符以外，字符串的所有头部字串。
- 后缀：除第一个字符以外，字符串的所有尾部字串。
- 局部匹配值：前缀和后缀的最大公共元素长度。
上面以“ABCDABD”为例来了解这三个概念：
局部匹配值的作用：
挪动位数=已匹配胜利的字符数-失配字符的上一个字符所对应的局部匹配值 即：move=(j-1)-next[j-1]
根据上述办法失去模式串“abcac”的局部匹配值为00010。写成数组的模式，就失去了next数组：
| 字符 | a | b | c | a | c |
|---|---|---|---|---|---|
| next | 0 | 0 | 0 | 1 | 0 |
批改next数组：
| 字符 | a | b | c | a | c |
|---|---|---|---|---|---|
| next | 0 | 0 | 0 | 1 | 0 |
| 右移1位 | -1 | 0 | 0 | 0 | 1 |
咱们留神到：
- 第一个元素右移后空进去的地位填入了-1。这是因为当第一个字符就不匹配时，只能往后挪动一位
- 最初一个元素在右移中溢出。因为原来的模式串中，最初一个元素的局部匹配值是其下一个元素应用的，但显然没有下一个元素，故能够舍去。（这里如果不舍去，将会有额定的作用，例如求循环节。）
这样，上式就被改写成move=(j-1)-next[j]（如果下标从0开始，则是move=j-next[j]）
即：挪动位数=已匹配胜利的字符数-失配字符所对应的局部匹配值
失配后与i从新对应的j的地位：j=j-move=j-((j-1)-next[j])=next[j]+1（如果下标从0开始，则是j=j-move=j-(j-next[j]) = next[j]）
对人而言，用上述办法很容易求next数组，但对于计算机来说，能够用一种更加高效的办法来求：
设T位子串，当next[j]曾经求得，next[j+1]的值能够分两种状况剖析。
- 若子串中字符$t_j$等于$t_i$，显然next[i+1]=j+1，因为j位以后T最长相等前后缀长度。
- 若$t_j$不等于$t_i$，将$t_{i-j+1}$…$t_i$当作主串，将$t_1$…$t_j$当作子串。相似于失配问题，需挪动子串，即令j=next[j]，持续进行比拟，若满足（1），则求得next[j+1]。
KMP算法仅在主串与子串有很多“局部匹配”时才显得更高效，其次要长处是主串不回溯。
代码
import java.util.Scanner;// //下标从0开始，只找第一个呈现的匹配后果publicclass KMP{ static int sLen; static int pLen; static char[] S = new char[1000009]; static char[] P = new char[10009]; static int[] next = new int[10009]; static void GetNext() { next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { if (k == -1 || P[j] == P[k]) { k++; j++; next[j] = k; } else { k = next[k]; } } } static int KMP() { int i = 0; int j = 0; while (i < sLen && j < pLen) { if (j == -1 || S[i] == P[j]) { i++; j++; } else { j = next[j]; } } if (j == pLen) return i - j + 1; //下标是从0开始的 else return -1; }public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("请输出主串："); String s1 = scan.nextLine(); sLen = s1.length(); S = s1.toCharArray(); System.out.print("请输出子串："); String s2 = scan.nextLine(); pLen = s2.length(); P = s2.toCharArray(); GetNext(); System.out.println(KMP()); }}