LeetCode——实现 strStr()【KMP算法实现】 LeetCode

文章图片

写在前面的话：不知道为啥LeetCode会分类到简单题，深坑题。网上KMP算法代码在LeetCode存在各种问题，dubug了两天。
【LeetCode——实现 strStr()【KMP算法实现】】在理论层面分为两种KMP算法：
①string[0]为字符串长度——《大话数据结构》
②string[0]为第一个元素——本文代码

//Java class Solution { public int strStr(String haystack, String needle) { int tarsize = needle.length(); //短字符串 int scrsize = haystack.length(); //长字符串 if(tarsize == 0)//短字符串是0 return 0; if(tarsize > scrsize)//短字符串比长字符串长 return -1; if(tarsize == scrsize && needle.equals(haystack))//两个字符串相同 return 0; int start = 0; //长字符串的和短字符串比较的第一个字符 int i = 0; //长字符串的和短字符串正在比较的相对第一个位置 int[] next = getNext(needle); //得到next数组 while (start <= scrsize - tarsize) { if(haystack.charAt(start + i) == needle.charAt(i)) { i++; if(i == tarsize) return start; } else { start = start + i - next[i]; i = i > 0 ? next[i] : 0; } } return -1; }public int[] getNext(String needle) { int tarsize = needle.length(); int[] next =new int[tarsize]; next[0] = -1; if(tarsize > 1) next[1] = 0; int i = 2; int j = 0; while(i < tarsize) { if(needle.charAt(i-1) == needle.charAt(j))// { next[i] = j+1; j++; i++; } else if(j > 0) { j = next[j]; } else { next[i] = 0; i++; } } return next; } }

//C++ class Solution { private: void buildKMPTable(const string & s, vector &KMP_Table) { int sSize = s.size(), i=2, j=0; KMP_Table[0] = -1; if(sSize>1) KMP_Table[1] = 0; while(i0) j = KMP_Table[j]; else KMP_Table[i++] = 0; } } public: int strStr(string haystack, string needle) { int start=0, i=0, hSize = haystack.size(), nSize = needle.size(); if(hSize KMP_Table(nSize, 0); buildKMPTable(needle, KMP_Table); while(start<=hSize-nSize) { if(haystack[start+i]==needle[i]) { if(++i == nSize) return start; } else { start = start+i-KMP_Table[i]; i= i>0?KMP_Table[i]:0; } } return -1; } };

普通算法【字符逐个比较】

int strStr(string haystack, string needle) { if (haystack.size() < needle.size()) return -1; if (needle.size() == 0 | haystack == needle) return 0; int len_hay = haystack.size(); int len_nee = needle.size(); for (unsigned i = 0; i < haystack.size() - len_nee + 1; i++) { if(haystack.substr(i,len_nee) == needle) return i; } return -1; }