大话数据笔记
第5章
1、串的存储结构是用一组地址连续的存储单元来存储串中的字符序列的。
2、KMP算法：
首先，对于这个问题有一个很单纯的想法：从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。这有什么难的？
我们可以这样初始化。之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤。基于这个想法我们可以得到以下的程序：
/**
* 暴力破解法
* @param ts 主串
* @param ps 模式串
* @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1
*/
public static int bf(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
while (i < t.length && j < p.length) {
if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
i++;
j++;
} else {
i = i - j + 1; // 一旦不匹配，i后退
j = 0; // j归0
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
* 暴力破解法
* @param ts 主串
* @param ps 模式串
* @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1
*/
public static int bf(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
while (i < t.length && j < p.length) {
if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
i++;
j++;
} else {
i = i - j + 1; // 一旦不匹配，i后退
j = 0; // j归0
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
柠檬微趣公司福利 1110人发布