代码随想录-04-字符串-06.实现strStr()

实现strStr()

实现KMP算法，进行模式串匹配

思路

• 明确：前缀、后缀、最长公共前后缀的概念
• 建立next数组，以便在每次匹配不成功时，尽可能将模式串向右滑动
• 将模式串和文本串进行匹配，文本串是一直向后匹配的，这也就是为什么KMP算法的效率很高的原因

---

实现难点

1. 建立next数组
2. 在模式串和文本串进行匹配的过程中，面对每一轮的处理。1和2的处理方式都是一样的。
   1. 如果不同，根据next数组查找下一个待匹配的位置j = next[j - 1];
   2. 如果相同，就直接j++;

---

代码

class Solution {
public:int strStr(string haystack, string needle) {if (haystack.size() < needle.size())return -1;vector<int> next(needle.size(), 0);getNext(next, needle);int j = 0;for (int i = 0; i < haystack.size(); i++) {while (j > 0 && haystack[i] != needle[j]) {j = next[j - 1];}if (haystack[i] == needle[j]) {j++;}if (j == needle.size()) {return i - needle.size() + 1;}}return -1;}void getNext(vector<int>& next, string needle) {int j = 0;for (int i = 1; i < needle.size(); i++) {while (j > 0 && needle[i] != needle[j]) {j = next[j - 1];}if (needle[i] == needle[j]) {j++;}next[i] = j;}}
};

Java

class Solution {public int strStr(String haystack, String needle) {if (haystack.length() < needle.length()) {return -1;}int[] next = initNext(needle);int cur = 0;for (int i = 0; i < haystack.length(); i++) {while (cur > 0 && haystack.charAt(i) != needle.charAt(cur)) { // 修正条件cur = next[cur - 1];}if (haystack.charAt(i) == needle.charAt(cur)) { // 修正条件cur++;}if (cur == needle.length()) { // 修正条件return i - needle.length() + 1; // 修正返回值}}return -1;}public int[] initNext(String needle) {int[] res = new int[needle.length()];res[0] = 0;int fast = 0;for (int i = 1; i < needle.length(); i++) {while (fast > 0 && needle.charAt(fast) != needle.charAt(i)) {fast = res[fast - 1];}if (needle.charAt(fast) == needle.charAt(i)) {fast++;}res[i] = fast;}return res;}
}