数据结构-串
目录
数据结构-串
什么是串？
串：即字符串（String），是由零个或多个字符组成的有限序列。
子串：字符串中任意个连续的字符组成的子序列称为该字符串的「子串」。
子串的位置：子串的第一个字符在主串中的位置。
主串：包含子串的串。
字符串的子串和子序列有什么区别？
- 字符串的子串：必须是连续的一段
- 字符串的子序列：可以不连续，但是相对次序不能乱
字符串匹配
字符串匹配：又称模式匹配，可以简单理解为，给定字符串 T 和 p，在主串 T 中寻找子串 p。主串 T 又被称为「文本串」，子串 p 又被称为「模式串」。
BF算法
BF算法：Brute-Force算法，又称蛮力算法。
基本思想：从主串和模式串的第一个字符开始比较，若相等，则继续比较两者的后续字符。否则从主串的第二个字符开始和模式串的第一个字符开始比较，重复上述过程，直到模式串的字符全部匹配完，则说明匹配成功。或主串中的字符全部比较完，则匹配失败。
- 什么时候退出循环？
当主串或者模式串遍历完成时:i < mainChars.length && j < patternChars.length - 如何计算出回溯时，主串的位置？
i-j+1 - 如何判断匹配成功
模式串的字符全部匹配完：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.length
return i - j;
}
return -1;
}