数据结构-串

什么是串？

串：即字符串（String），是由零个或多个字符组成的有限序列。

子串：字符串中任意个连续的字符组成的子序列称为该字符串的「子串」。

子串的位置：子串的第一个字符在主串中的位置。

主串：包含子串的串。

字符串的子串和子序列有什么区别？

• 字符串的子串：必须是连续的一段
• 字符串的子序列：可以不连续，但是相对次序不能乱

字符串匹配

字符串匹配：又称模式匹配，可以简单理解为，给定字符串 T 和 p，在主串 T 中寻找子串 p。主串 T 又被称为「文本串」，子串 p 又被称为「模式串」。

BF算法

BF算法：Brute-Force算法，又称蛮力算法。

基本思想：从主串和模式串的第一个字符开始比较，若相等，则继续比较两者的后续字符。否则从主串的第二个字符开始和模式串的第一个字符开始比较，重复上述过程，直到模式串的字符全部匹配完，则说明匹配成功。或主串中的字符全部比较完，则匹配失败。

1. 什么时候退出循环？
   当主串或者模式串遍历完成时:i < mainChars.length && j < patternChars.length
2. 如何计算出回溯时，主串的位置？
   i-j+1
3. 如何判断匹配成功
   模式串的字符全部匹配完：j == patternChars.length

public static int firstIndex(String mainStr, String patternStr) {// 空值检查if (mainStr == null || patternStr == null) {return -1;}// 空模式串处理：空串是任意串的子串if (patternStr.length() == 0) {return 0;}char[] mainChars = mainStr.toCharArray();char[] patternChars = patternStr.toCharArray();// 主串的索引int i = 0;// 模式串的索引int j = 0;while (i < mainChars.length && j < patternChars.length) {if (mainChars[i] == patternChars[j]) {// 字符匹配成功，继续比较下一个字符i++;j++;}else {// 字符匹配失败，主串回退到上次匹配开始位置的下一个字符重新开始匹配i = i - j + 1;j = 0;}}if (j == patternChars.length) {// 匹配成功: 模式串的字符全部匹配完：j == patternChars.lengthreturn i - j;}return -1;
}