串是由0个或者多个字符组成的有限序列，又名叫字符串。
串的比较：
串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
计算机中常用的ASCII编码，由8位二进制数表示一个字符，总共可以表示256个字符。
对于以英语为主的国家来说，ASCII已经足够使用，但对于其他语种的国家来说，显然是不够的。
所以出现了Unicode编码，使用16位二进制数来表示一个字符，这样总共可以表示2的16次方个字符，同时兼容ASCII编码。
所以在比较两个串是否相等时，必须是它们串的长度以及各个对应位置都相等时，才算相等。
如happen < hyppy, e的ASCII 码为101， 而y的AscII码为121，显然e < y。
串的存储结构：
串的存储结构有顺序存储和链式存储两种结构。
使用顺序存储则串的长度是不可更改的，在进行字符串拼接时往往需要生成一个新串。
使用链式存储，一个结点对应一个字符，会造成很大的空间浪费。
串的匹配算法：
我们常常在文章、网页中查找某个单词，这种字串的定位操作通常称作串的模式匹配。
在普通模式匹配算法，需要将主串的每一个字符作为字串开头，与要匹配的字符串进行匹配。
这个过程中，会对主串进行大循环，以每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成。
假设S主串长度为N，T字串字符长度为M，则整个算法时间复杂度为O((N-M+1)*M)。
public static int patternMatch4Simple(String sourceString, String targetString) {
checkParam(sourceString, targetString);
char[] sourceChars = sourceString.toCharArray();
char[] targetChars = targetString.toCharArray();
int index = -1;
int offset = sourceChars.length - targetChars.length;
boolean contains = true;
for (int i = 0; i <= offset; i++) {
for (int j = 0; j < targetChars.length; j++) {
if (sourceChars[i + j] != targetChars[j]) {
contains = false;
break;
}
}
if (contains) {
index = i;
break;
}
contains = true;
}
return index;
}
在字串与主串存在许多"部分匹配"的情况下，简单模式匹配便会有许多不必要的重复匹配。如主串为S = ‘ababcdefgh‘, 子串T = ‘ababe‘时。
KMP算法就是为了避免这些重复匹配而生的，按照KMP算法，在主串S上进行比较后，下标是不会回溯的，仅仅只是回溯子串T的下标。
通过对T回溯的设计，在主子串存在部分匹配的情况下，可以避免重复匹配。T回溯有一套自己的算法，T中每个字符都有自己的回溯坐标，
这个坐标取决于当前字符之前的串的前后缀的相似度。
假设主串长度为N，子串长度为M，算法仅需分别对其做一次循环，时间复杂度为O(N+M)。
public static int patternMatch4KMP(String sourceString, String targetString) {
// check param
checkParam(sourceString, targetString);
// init kmp array for
char[] targetChars = targetString.toCharArray();
int[] kmpArray = new int[targetChars.length];
for (int i = 0; i < targetChars.length; i++) {
if (i == 0) {
kmpArray[i] = 0;
} else if (i == 1) {
kmpArray[i] = 1;
} else {
int match = 0;
for (int j = 0; j < i - 1; j++) {
if (targetChars[j] != targetChars[i - 1 - j]) {
break;
}
match++;
}
kmpArray[i] = match + 1;
}
}
char[] sourceChars = sourceString.toCharArray();
int index = -1;
int sourceCharIndex = 0;
for (int j = 0; j <= targetChars.length;) {
if (j == targetChars.length) {
index = sourceCharIndex - j;
break;
}
if (sourceCharIndex == sourceChars.length) {
break;
}
if (targetChars[j] == sourceChars[sourceCharIndex]) {
sourceCharIndex++;
j++;
continue;
}
if (targetChars[j] != sourceChars[sourceCharIndex]) {
int kmp = kmpArray[j];
if (kmp == 0) {
sourceCharIndex++;
j = 0;
} else {
j = kmp - 1;
}
}
}
return index;
}
经过更多的实践，我们发现KMP算法中，在某种情况下仍然存在重复的匹配操作。即子串下标回溯时，回溯坐标不对。
改进后的KMP算法，对回溯坐标点进行再度计算，减少了回溯时重复匹配。
public static int patternMatch4KMPEnhance(String sourceString, String targetString) {
// check param
checkParam(sourceString, targetString);
// init kmp array for
char[] targetChars = targetString.toCharArray();
int[] kmpArray = new int[targetChars.length];
int[] kmpEnhanceArray = new int[targetChars.length];
for (int i = 0; i < targetChars.length; i++) {
if (i == 0) {
kmpArray[i] = 0;
kmpEnhanceArray[i] = 0;
} else {
int match = 0;
for (int j = 0; j < i - 1; j++) {
if (targetChars[j] != targetChars[i - 1 - j]) {
break;
}
match++;
}
kmpArray[i] = match + 1;
if (targetChars[kmpArray[i] - 1] == targetChars[i]) {
kmpEnhanceArray[i] = kmpArray[kmpArray[i] - 1];
} else {
kmpEnhanceArray[i] = kmpArray[i];
}
}
}
char[] sourceChars = sourceString.toCharArray();
int index = -1;
int sourceCharIndex = 0;
for (int j = 0; j <= targetChars.length;) {
if (j == targetChars.length) {
index = sourceCharIndex - j;
break;
}
if (sourceCharIndex == sourceChars.length) {
break;
}
if (targetChars[j] == sourceChars[sourceCharIndex]) {
sourceCharIndex++;
j++;
continue;
}
if (targetChars[j] != sourceChars[sourceCharIndex]) {
int kmp = kmpEnhanceArray[j];
if (kmp == 0) {
sourceCharIndex++;
j = 0;
} else {
j = kmp - 1;
}
}
}
return index;
}
有关KMP数组坐标的数学公式与推导，参考大话数据结构。
原文：https://www.cnblogs.com/cd-along/p/14791929.html