（字符串）LC实现 strStr()

题目

方法一：子串直接比较

失配时，haystack定位到下一个字符，needle定位到第一个字符，重新尝试匹配

public int strStr(String haystack, String needle) {
    if(needle.length() == 0)return  0;char[] hChars = haystack.toCharArray();char[] nChars = needle.toCharArray();int hLen = hChars.length , nLen = nChars.length;int i = 0 , k = i ;boolean founded = false;for(; i < hLen && !founded; i++){
    if(hLen - i < nLen)break;founded = true;k = i;for(int j = 0; j < nLen; j++,k++){
    if(hChars[k] != nChars[j]){
    founded = false;break;}}}return founded ? i - 1 : -1;}

• 时间复杂度：O（mn）
• 空间复杂度：O（1）

方法二：KMP算法

构造next数组，失配时，needle定位到next[k]处（假设在k处失配）重新尝试匹配

public  int strStr(String haystack, String needle) {
    if(needle.length() == 0)return  0;char[] hChars = haystack.toCharArray();char[] nChars = needle.toCharArray();int hLen = hChars.length , nLen = nChars.length;// 求next数组int[] next = new int[nLen];next[0] = -1;int i = 0 , j = -1;while(i < nLen - 1){
    if(j == -1 || nChars[i] == nChars[j])next[++i] = ++j; // j一直为nChars[i]的next值else j = next[j];}// strStr()i = 0;j = 0;while(j < nLen && hLen - i >= nLen - j){
    if(nChars[j] == hChars[i]){
    i++;j++;}else {
    j = next[j];if(j == -1){
    j = 0;i++;}}}return j == nLen  ? i - nLen : -1;}

• 时间复杂度：O（m+n）
• 空间复杂度：O（n）n为needle长度