前言计算机中非数值处理的对象基本上是字符串数据，随着语言加工程序的发展，字符串作为变量型出现在许多编程语言中，同时也产生了一系列的字符串操作。 在日常编程中，名称、位置等信息都表示为字符串，而文本框、输入框等都是以字符串数据为处理对象。
什么是字符串字符串(字符串)？ 或直接称为字符串。是由零个或多个字符组成的有限序列
字符串中的字符数称为字符串长度，如果字符数为0，则该字符串称为空串。
由一个或多个空格组成的字符串称为空格串。 请注意，空字符串看起来没有内容，但与空间列不同。
字符串str1=' jack '； String str2='123@qq.com '； String str3=' '； //空字符串String str4=' '； //空白字符串(一个空白字符)列中任意字符(包括0个)连续的子串被称为该字符串的子串，包含子串的字符串被称为主串，子串的第一个
String str1='helloworld！' ； String str2='ll '； //str2是str1的子字符串，如果str1中的位置为2且两个字符串的值相等，则称为两个字符串相等。
String str1='WuHan '； String str2='WuHan '； //str1和str2相等的字符串表示和实现字符串不仅可以表示特定信息的常数，还可以表示为变量。 字符串通常有三种机内表示方法。
定长逐次存储是指线性表那样的逐次存储结构，在一系列地址连续的存储单元中存储一系列文字字符串。
堆分配内存是指按一系列地址在连续的存储单元中存储一系列字符串，但内存空间在程序运行时动态分配。
区块链表示类似于线性表的链存储结构，采用链表方式存储串值。
的字符串模式匹配模式匹配是数据结构中字符串的基本运算，是各种字符串处理系统中最重要的操作之一。
将s作为给定的主串、t作为给定的部分串，在主串s中寻找等于部分串t的串的过程是模式匹配的过程，t被称为模式串。 如果在s中找到t子串，则表示匹配成功，函数返回t在s中首次出现的存储位置，否则匹配失败，返回-1。
虽然有很多字符串匹配算法，但这里只介绍两种最常见的算法。
BF(brute-force )算法原理最朴素的想法是列举主字符串的各字符，以各字符为起点尝试与模式串的第一个字符一致。 如果相同，则继续主字符串与模式列中的下一个字符匹配，如果不同，则从主字符串中的下一个字符再次开始匹配。
如果在一次匹配过程中与模式列中的最后一个字符匹配，则匹配成功，如果不匹配，则失败。
代码实现publicintmybfindexof(strings，String T ) { int n=S.length )、m=T.length )； //pos是本轮一致的主字符串的开头字符位置，主字符串长度减去模式字符串长度后的差//posn-m时，一定会失败，因此for(intpos=0； pos=n - m； POS(intj=0； for (； j m； j ) if(s.Charat ) posj )！=t.Charat(j ) ) break； 匹配//模式串中的最后一个字符意味着匹配了if(j==m )返回pos }返回- 1； }动图展示
复杂度分析时间复杂度： o(nm ) m ) o ) n-m (m ) o(nm ) m )，列举主字符串的开始字符时间复杂度为o ) n
− m ) O(n - m) O(n−m) ，匹配模式串的时间复杂度为 O ( m ) O(m) O(m) 。空间复杂度： O ( 1 ) O(1) O(1) ，仅使用常数空间保存一些变量。
KMP（Knuth-Morris-Pratt） 算法 原理 暴力解法的问题在暴力求解时，每当一轮匹配过程出现字符不等时，都会以主串的下一个字符为起始字符开启新的一轮匹配。考虑一个极端的情况，主串为 aaaaaaaaaaaaaaab ，模式串为 aaaaab ，每一轮匹配都会比较到模式串的最后一个字符 b ，然后发现不相等，继续下一轮匹配。
不难发现，这里存在明显的问题，那应该如何改进呢？
优化的地方我们先来看看匹配的具体过程，下面是第一轮匹配失配时的状态：
按照暴力匹配的方式，会从主串的第二个字符重新开始匹配：
事实上，我们很轻易地就会观察到（其实是 D.E.Knuth，J.H.Morris 和 V.R.Pratt 三位天才观察到的），已经匹配过的主串中的字符和模式串中的字符是有重叠的，没有必要再次匹配：
因此指向主串的指针不用回溯，指向模式串的指针不必从头开始，这样就大大提高了效率。
前缀表和前缀函数现在我们知道了 BF 算法可以优化的地方，就是找到每次失配时已经匹配过的主串中的字符和模式串中的字符中重叠的部分，这部分不需要再次比较。
这里所说的重叠部分就是字符串的公共前缀和后缀，模式串的每一个子串（从下标0开始）的最长公共前后缀的长度用一个一维数组表示就构成了模式串的前缀表，或者编程时习惯性命名为 next 数组 。
在上面的例子中，第一次失配时，字符串匹配到了模式串的 b 字符，此时已经匹配过的字符串为 aaaaa ，它的最长公共前后缀为 aaaa 。
看了上面的动图应该能明白为什么说公共前后缀部分为什么不需要再次比较，但是我们还不清楚怎么求公共前后缀，下面我们看看一个更常规的例子，模式串 abaabcac 的前缀表是怎么得来的的。
上面得到前缀表的方式是肉眼观察的，原理也很简单，就是从字符串两边开始分别向另一边逐个比较，相等就继续，否则就停止，这样就可以得到每一个子串的最长公共前后缀的长度，不过这个时间复杂度很高，有没有可能简化这个过程呢？
答案是，当然有。D.E.Knuth，J.H.Morris 和 V.R.Pratt 三位天才给出了线性时间复杂度下求解 next 数组的方法，它是 KMP 算法的核心，称为前缀函数。
下面我们看看，线性时间复杂度下 next 数组的求解过程。
起始 next[0] = 0，指针 j 指向位置0，指针 i 指向位置1；
如果 T[j] == T[i]，指针 i、j 均向后移动，重复该过程，直到 T[j] ！= T[i] 或者 i 指向模式串末尾；
如果 T[j] ！= T[i]，指针 j 指向上一位置的 next 数组对应的值，即 j = next[j - 1]，重复该过程，直到 T[j] == T[i] 或者 j == 0；
如果 j == 0，此时 T[j] ！= T[i] ，指针 j 不动，指针 i 继续向后移动。
代码实现 public int myKMPIndexOf(String S, String T) { int n = S.length(), m = T.length(); if (m == 0) return 0; // 求 next 数组 int[] next = new int[m]; for (int i = 1, j = 0; i < m; i++) { while (j > 0 && T.charAt(i) != T.charAt(j)) { j = next[j - 1]; } if (T.charAt(i) == T.charAt(j)) { j++; } // 前 i + 1 个字符组成的字符串，最长公共前后缀长度为 j next[i] = j; } // 匹配过程 // 指向主串的指针 i 一直向后，不回溯 for (int i = 0, j = 0; i < n; i++) { // 如果失配，根据 next 数组更新模式串指针 j while (j > 0 && S.charAt(i) != T.charAt(j)) { j = next[j - 1]; } // 如果匹配，模式串指针 j 后移 if (S.charAt(i) == T.charAt(j)) { j++; } // 匹配到模式串最后一个字符意味着匹配成功 if (j == m) return i - m + 1; } return -1;} 动图展示 复杂度分析时间复杂度： O ( m + n ) O(m + n) O(m+n) ，其中 n 为主串的长度，m 为模式串的长度。
空间复杂度： O ( m ) O(m) O(m) ，使用一维数组存储模式串的前缀表。
>下一篇：