字符串是一种特殊的线性表，即元素都是”字符“的线性表。
字符是组成字符串的基本单位，字符的取值依赖于字符集，例如二进制的字符集为0,1，则取值只能为(0,1)，再比如英语语言，则包括26个字母外加标点符号。
例如"abcde"就是一个字符串，其中'a','b','c','d','e'都分别是串中的字符，串的长度是5。
线性表的存储结构同样适用于字符串，但是因为链式结构的额外开销，大部分情况下会采用顺序结构。
子串定义：串中任意个连续的字符组成的子序列称为该串的子串
例如:abc 就是 abcde的其中一个子串
特殊子串：
1.空字符串是任意串的子串
2.任意串S都是S本身的子串
3.真子串：非空且不为自身的子串(即不属于1，2两种情况下的)
关于字符串的其他运算不多做说明了，大多数人都太熟悉了，来看看难点的字符串的模式匹配以及实现算法吧。
模式匹配是数据结构中字符串的一种基本运算，给定一个串，要求在某个字符串中找出与该串相同的所有子串，这就是模式匹配。
假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。
假设T的长度为n，P的长度为m，比较容易想到的一个方法是初始时设置i=0&j=0，然后同时增大i与j判断n_i与m_j是否相等，直到j=m-1，如果一直相等，则匹配成功，如果n_i与m_j不相等，则设置i=i+1,j=0重新开始匹配，直到找到结果，或者i=n-m为止。
这种方式被称为BF算法(Brute Force)，也被叫做朴素模式匹配算法或穷举法，代码实现如下(java)：
package top.zhanglugao.patternmatch;
public class PatternMatch {
public static void main(String[] args) {
//目标串T
String T="abacbcdhjk";
//模式P
String P="abad";
String P2="cbcd";
int i = bruteForcePatternMatch(P, T);
System.out.println(i);
i=bruteForcePatternMatch(P2,T);
System.out.println(i);
//运行结果分别是-1与3 程序无误
}
/***
*
* @param P 模式P
* @param T 目标串T
* @return
*/
public static int bruteForcePatternMatch(String P,String T){
int n=T.length();
int m=P.length();
//如果P的长度大于T 不可能查找成功返回-1
if(n<m){
return -1;
}
//i的最大值是n-m 这之后长度不够了
for(int i=0;i<n-m;i++){
//这里为了便于理解 采用了双层循环一个个字符比较的方式 实际上直接用T.substring(i,i+m)与P比较就可以了，里面这层嵌套没必要
for(int j=0;j<m;j++){
if(P.substring(j,j+1).equals(T.substring(i+j,i+j+1))){
if(j==m-1){
//匹配成功了
return i;
}
//相等 继续判断下个字符
}else{
//匹配到不相等 可以跳出内层循环了
break;
}
}
}
return -1;
}
}
下面来分析一下这个算法的复杂度：
匹配成功+最坏的情况下，如果直到最后一次才成功，那么i的值为(n-m)+1,j的值为m,总共比较次数为((n-m)+1)*m次，时间复杂度为O(n*m)。
匹配成功+最好的情况是T的前m个字符与P相等，总比较次数为m，时间复杂度为O(m)。
匹配失败+最坏的情况与匹配成功时相同。
匹配失败+最好的情况是每次比较第一个字符时就发现不相等，那么比较次数为(n-m)+1，时间复杂度为O(n)。
上面的穷举法是没有问题的，但不够好，如果是人为来寻找的时候，不会每次都将i回溯到i+1的位置。看下面比较的图。
在红色的位置出现了不匹配的情况，如果按照上面的朴素算法，会将i右移一位重新比较，但我们可能一眼就能看出来应该将i右移3位再比较，再之前的比较是无意义的，那么这其中有没有规律呢？我们尝试多观察一些同样的情况。
这个例子，我们显然应该右移两位，因为T中C前面的A与P开头的A是一致的。
这里应该右移三位，达到下面的状态：
仔细观察下可以发现这样的数学规律，如果存在一个常数k，使得T[i]之前k位与P开头的前k位相同，则可以设置j=k,继续比较。
也就是j要移动到的下一个位置k，存在最前面的k个字符与j之前的k个字符时相等的。即P[0]到P[k-1]==P[j-k]到P[j-1]
用图来表示的话就是下面这样：
其实也就是当匹配到P[j]!=T[i]时，其实意味着P位置j之前与T[i-j]是相等的，即T[i-j ~ i-1] == P[0 ~ j-1]，再根据前面的P[0 ~ k-1]==P[j-k ~ j-1]可以得到T[i-k ~ i-1] == P[0 ~ k-1]，这也是为什么可以跳过前面的部分直接时j=k继续比较。
接下来的问题是怎么求解k了，这样我们才能顺序编写程序来实现逻辑。
再根据前面的P[0 ~ k-1]==P[j-k ~ j-1]，我们可以确定k的值只跟当前模式P以及当前j的值有关，而跟目标串T没有关系，而且对于每个位置j有确定的一个k。假设存储k的数组为next[]
举个例子，当P=‘abaabcac’时，其各位置的next值计算过程为：
a j=0, 特殊情况，设置next(j)=-1
b j=1, 满足0<k<1的整数k不存在，next(j)=0
a j=2, 子串P1 != P0，k不存在，next(j)=0
a j=3, 存在且仅存在子串P2==P0，next(j)=k=1
b j=4, 存在且仅存在子串P3==P0，next(j)=k=1
c j=5, 存在最大子串P3P4==P0P1，next(j)=k=2
a j=6, 不存在要求子串，next(j)=0
c j=7, 存在且仅存在子串P6==P0，next(j)=k=1
尝试用java写个最弱智版本的求next数组的办法，之后我们再看看能不能优化，代码如下：
/***
* 获得next数组 对于循环中的j 寻找P[0]到p[k-1]=p[j-k]=p[j-1] 如果不存在这样的k k=0 因为java中substring方法含头不含尾的特性 对于尾部要进行+1的特殊处理
* @param P 模式P
* @return
*/
public static Integer[] getNextArray(String P) {
Integer[] next = new Integer[P.length()];
next[0]=-1;
for (int j = 1; j < P.length(); j++) {
for (int k = j-1; k >0; k--) {
System.out.println("j="+j+"&k="+k+"&P(0)到P(k-1)="+P.substring(0, k-1+1)+"&P(j)到P(j - 1)="+P.substring(j - k, j - 1+1));
if (!P.substring(0, k-1+1).equals("")&&P.substring(0, k-1+1).equals(P.substring(j - k, j - 1+1))) {
next[j] = k;
System.out.println("j="+j+"&k="+k);
break;
}
}
if (next[j] == null) {
//没查找到
System.out.println("没查找到 j=" + j);
next[j] = 0;
}
}
return next;
}这个方法显然效率不能让人接受，我们继续寻找一下规律。还是对于P=‘abaabcac’时，
a j=0, 特殊情况，设置next(j)=-1
b j=1, 满足0<k<1的整数k不存在，next(j)=0,P[next(j)]=a!=P[j]
a j=2, 子串P1 != P0，k不存在，next(j)=0,P[next(j)]=a=P[j]
a j=3, 存在且仅存在子串P2==P0，next(j)=k=1,P[next(j)]=b!=P[j]
b j=4, 存在且仅存在子串P3==P0，next(j)=k=1,P[next(j)]=b=P[j]
c j=5, 存在最大子串P3P4==P0P1，next(j)=k=2,P[next(j)]=a!=P[j]
a j=6, 不存在要求子串，next(j)=0,P[next(j)]=a=P[j]
c j=7, 存在且仅存在子串P6==P0，next(j)=k=1,P[next(j)]=b!=P[j]
用递推法可以发现的规律是(当然我这种凡人是发现不了的，书上说了我才能确认。T_T)：
，像上边的例子，我们已经不可能找到[ A，B，A，B ]这个最长的后缀串了，但我们还是可能找到[ A，B ]、[ B ]这样的前缀串的。所以这个过程像不像在定位[ A，B，A，C ]这个串，当C和主串不一样了（也就是k位置不一样了），那当然是把指针移动到next[k]啦，所以只需要执行k=next[k]经过优化过的求next数组的代码就变成了：
public static Integer[] getNextArray2(String P) {
char[] p=P.toCharArray();
Integer[] next = new Integer[P.length()];
next[0] = -1;
int j = 0;
int k = -1;
while (j < P.length() - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}下面就可以写KMP算法了，代码实现如下：
public static int KMP(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串T的位置
int j = 0; // 模式串P的位置
Integer[] next = getNextArray2(ps);
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
i++;
j++;
} else {
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}算法分析：
由于j=next[j]，每执行一次必然使得j减少，而使得j增加的操作只有j++;那么如果j=next[j]执行次数如果超过n(T的长度)次就会变成负数了。所以时间效率为O(n)，同理求Next数组时间复杂度为O(m)，所以KMP算法的时间复杂度为O(n+m)，对比朴素的O(m*n)提升很大了。
ps:花了一整天，哎。CSDN针对我啊，每次都要审半天。