【LeetCode】字符串匹配

给定目标串 haystack 和模式串 needle ，返回 needle 在 haystack 中第一次出现的位置下标，若 needle 不是 haystack 的子串则返回 -1。

1. Brute-Force Algorithm（暴力算法 / 简单模式匹配）

我自己写了一种双层循环的

 int strStr(string haystack, string needle) {

     if (needle.empty()) return ;

     int m = haystack.size(), n = needle.size();

     for (int i = ; i <= m - n; i++) {

         for (int j = ; j < n; j++) {

             if (needle[j] != haystack[i + j])

                 break;

             if (j == n - )

                 return i;

         }

     }

     return -;

 }

看了答案发现了一种更高效的方法，虽然时间复杂度同样是 O(m*n)，但只要一层循环，非常Nice！

 int strStr(string haystack, string needle) {

     if (needle.empty()) return ;

     int i = , j = ;

     int m = haystack.size(), n = needle.size();

     while (i < m && j < n) {

         if (haystack[i] == needle[j]) {

             i++;

             j++;

         } else {

             i = i - j + ;

             j = ;

         }

         if (j == n)

             return i - j;

     }

     return -;

 }

2. KMP算法

算法讲解可以参考 http://www.61mon.com/index.php/archives/183/ ，讲解的已经很好了。

KMP的时间复杂度仅为 O(m+n)，因为当出现子串与主串某处不匹配时，并不会将遍历主串的下标 i 回溯，而是利用得到的 next 数组将模式子串向右“滑动”尽可能远的一段距离，继续进行比较，提高了效率。

next 数组的求解是关键，它是基于模式子串的最长前后缀，next[i] = needle[0] 到 needle[i - 1] 的字符串的最长相同前后缀的长度。

 void getNext(string needle, vector<int> &next) {

     int i = , j = -;

     // j 表示最长相同前后缀的长度

     next[] = j;

     while (i < needle.size()) {

         // j == -1 为边界条件判断， j = next[j] 可能使 j 退回到 -1

         if (j == - || needle[i] == needle[j]) {

             i++;

             j++;

             next[i] = j;

         } else {

             j = next[j];

         }

     }

 }

 int strStr(string haystack, string needle) {

     if (needle.empty()) return ;

     int i = , j = ;

     int m = haystack.size(), n = needle.size();

     vector<int> next(n + );

     getNext(needle, next);

     while (i < m && j < n) {

         if (j == - || haystack[i] == needle[j]) {

             i++;

             j++;

         } else {

             j = next[j];

         }

         if (j == n)

             return i - j;

     }

     return -;

 }

改进的KMP算法

 void getNextval(string needle, vector<int> &nextval) {

     int i = , j = -;

     nextval[] = j;

     while (i < needle.size()) {

         if (j == - || needle[i] == needle[j]) {

             i++;

             j++;

             // 生成 nextval 数组

             if (needle[i] != needle[j])

                 nextval[i] = j;

             else

                 nextval[i] = nextval[j];

         } else {

             j = nextval[j];

         }

     }

 }

 int strStr(string haystack, string needle) {

     if (needle.empty()) return ;

     int i = , j = ;

     int m = haystack.size(), n = needle.size();

     vector<int> nextval(n + );

     getNextval(needle, nextval);

     while (i < m && j < n) {

         if (j == - || haystack[i] == needle[j]) {

             i++;

             j++;

         } else {

             j = nextval[j];

         }

         if (j == n)

             return i - j;

     }

     return -;

 }

巴特西

【LeetCode】字符串匹配

最新文章

热门文章