代码随想录第九天，继续字符串
今日任务
● 28. 实现 strStr()
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
trivial
库函数
return haystack.indexOf(needle);
String.indexOf() time complexity O(mn)
方法一 暴力解法
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) {
boolean flag = true;
for (int j = 0; j < m; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
}
时间复杂度均为： O( n * m) n 为haystack 长度，m为needle长度
空间复杂度：O(1)。我们只需要常数的空间保存若干变量
方法二 substring解法 与暴力解法相似
class Solution {
public int strStr(String haystack, String needle) {
int needleLen = needle.length();
char startChar = needle.charAt(0);
if(haystack.length() < needleLen) return -1;
for(int i = 0; i <= haystack.length() - needleLen; i++){
if(haystack.charAt(i) == startChar
&& haystack.substring(i,i + needleLen).equals(needle)){
return i;
}
}
return -1;
}
}
时间复杂度均为： O( n * m) n 为haystack 长度，m为needle长度
空间复杂度：O(1)。
方法三： KMP算法
kmp 最长相等前后缀. KMP主要应用在字符串匹配上。
主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容，是KMP的重点，也是prefix/next数组肩负的重任。
前缀表
next / prefix 数组就是一个前缀表（prefix table）
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
例子：
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
可以看出，文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。
如果暴力匹配，会发现不匹配，此时就要从头匹配了。
但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。
首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。
那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
前缀表如何记录
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
比如说有一个长度为5字符串 x = "ababc"，其中前缀有 ε（空串），a，ab，aba，abab；后缀有 ε（空串），c，bc，abc，babc，这样应该就很好理解了
前缀表就是存储当前字符相同前后缀的长度。
在当前例子中， 模式串为 aabaaf
模式串下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。
所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。
如何计算前缀表
在下标0位置，当前子串a，长度为一个字符，没有前缀与后缀，最长相同前后缀的长度为0。
在下标1位置，当前子串aa,长度为2， 最长相同前后缀分别为a,a,最长相同前后缀的长度为1。
在下标2位置，当前子串aab,长度为3，前缀为a,ab; 后缀为b, ab,没有相同前后缀，最长相同前后缀的长度为0。
在下标3位置，当前子串aaba, 长度为4，前缀为a,aa,aab;后缀为a,ba,aba, 最长相同前后缀为a,最长相同前后缀的长度为1。
在下标4位置，当前子串aabaa, 长度为5，前缀为a,aa,aab,aaba; 后缀为a,aa,baa,abaa, 最长相同前后缀为aa,最长相同前后缀的长度为2。
在下标5位置，当前子串aabaaf, 长度为6，前缀为a,aa,aab,aaba,aabaa; 后缀为f,af,aaf,baaf,abaaf, 无相同前后缀,最长相同前后缀的长度为0。
求得的最长相同前后缀的长度就是对应前缀表的元素，如图
可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
复杂度分析
其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大的提高的搜索的效率。
构造前缀表(next / prefix 数组)
构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：
初始化
处理前后缀不相同的情况
处理前后缀相同的情况
- 初始化
定义两个指针i和j，j指向后缀末尾位置，i指向前缀末尾位置。
int j = 0;
next[0] = 0;
next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）, 所以初始化next[0] = j
- 处理前后缀不相同的情况
因为j初始化为0，那么i就从1开始，进行s[i] 与 s[j]的比较。
所以遍历模式串s的循环下标i 要从 1开始，代码如下：
for(int i = 1, i < pattern.length(); i++)
如果 s[i] 与 s[j]不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回退。
怎么回退呢？
next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。
那么 s[i] 与 s[j] 不相同，就要找 j前一个元素在next数组里的值（就是next[j - 1]）。
所以，处理前后缀不相同的情况代码如下：
while(j > 0 && s[i] !=s[j]){
j = next[j - 1];
}
- 处理前后缀相同的情况
如果 s[i] 与 s[j ] 相同，说明找到了相同的前后缀，j 与i同时向后移动; 同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。
if(s[i] == s[j]){
j++;
}
next[i] = j;
整体代码如下：
public void getPrefix(int[] prefix, String s){
//1. 初始化
int j = 0;
prefix[0] = 0;
for(int i = 1; i < s.length(); i++){
//处理前后缀不同情况
while(j > 0 && s.charAt(j) != s.charAt(i)){
j = prefix[j - 1];
}
//处理前后缀相同情况
if(s.charAt(j) == s.charAt(i)){
j++;
}
prefix[i] = j;
}
}
}
求prefix / next 数组的时候就是相当于在用kmp，把 【0,j】 的前缀看成是模式串，把 【1,i】 的后缀看成是文本串，①文本串一直是每次循环+1，不会回退 ②模式串有时候可以通过next数组跳过前面几个字符直接比较，这两点就是kmp高效的地方
使用next数组来做匹配
在文本串s里 找是否出现过模式串t。
定义两个下标j 指向模式串t起始位置，i指向文本串s起始位置。
j = 0
i就从0开始，遍历文本串，代码如下：
for (int i = 0; i < s.size(); i++)
如果 s[i] 与 t[j + 1] 不相同，j就要从next数组里寻找下一个匹配的位置
while( j > 0 && s[i] != t[j] ) j = next[j ];
如果 s[i] 与 t[j ] 相同，那么i 和 j 同时向后移动
if(s[i] == t[j] ) j++;
如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了。要在文本串字符串中找出模式串出现的第一个位置 (从0开始)，所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。
if(j == (t.length() - 1)) return i - t.length() +1;
整体代码：
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length();
if(n == 0) return 0;
if(n < needle.length()) return -1;
//construct prefix array of needle
int[] prefix = new int[needle.length()];
getPrefix(prefix,needle);
int j = 0; //j指向 needle 的第一个位置
for(int i = 0; i < n; i++){
while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
j = prefix[j - 1]; //j回到前一位置的prefix值：当前最长相等前后缀
}
if(haystack.charAt(i) == needle.charAt(j)){
j++; //字符相同，j前进一步
}
if(j == needle.length()){//j成功走完needle，说明found needle in haystack
return i - needle.length() + 1;
}
}
return -1;
}
public void getPrefix(int[] prefix, String s){
//1. 初始化
int j = 0;
prefix[0] = 0;
for(int i = 1; i < s.length(); i++){
//处理前后缀不同情况
while(j > 0 && s.charAt(j) != s.charAt(i)){
j = prefix[j - 1];
}
//处理前后缀相同情况
if(s.charAt(j) == s.charAt(i)){
j++;
}
prefix[i] = j;
}
}
}
KMP 算法的复杂度为 O(m+n)。
KMP 之所以能够在 O(m+n) 复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。
空间复杂度部分O(m)，我们只用到了长度为 m 的数组保存前缀函数，以及使用了常数的空间保存了若干变量
