【内功】基础算法—

【内功】基础算法——字符串

[1] Manacher

求一个字符串中的最长回文子串。

讲解直接放ppt，复习能回忆起来就行。

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 string manacher(string& s) {
 8     vector<int> p(s.size(), 0);
 9     int mx = 0, dx = 0;
10     for (auto i = 1; i < s.size(); ++i) {
11         if (mx > i) {
12             p[i] = min( p[2*dx-i] , (int)mx-i);
13         } else {
14             p[i] = 1;
15         }
16         while (s[i+p[i]] == s[i-p[i]]) {
17             p[i]++;
18         }
19         if (p[i] + i > mx) {
20             mx = p[i] + i;
21             dx = i;
22         }
23     }
24     int index = -1, max_len = -1;
25     for (auto i = 1; i < s.size(); ++i) {
26         if (p[i] > max_len) {
27             index = i;
28             max_len = p[i];
29         }
30     }
31     max_len--; // P[i]-1正好是原字符串中回文串的总长度
32     int start = index - max_len;
33     int end = index + max_len;
34     string ans = "";
35     for (int i = start; i <= end; ++i) {
36         if (s[i] != '#') {
37             ans += s[i];
38         }
39     }
40 
41     cout << "s = ";
42     for (int i = 0; i < s.size(); ++i) {
43         cout << s[i] << " ";
44     }
45     cout << endl;
46     cout << "p = ";
47     for (int i = 0; i < s.size(); ++i) {
48         cout << p[i] << " ";
49     }
50     cout << endl;
51 
52     return ans;
53 }
54 
55 int main() {
56     string s;
57     cin >> s;
58     string tmp = "$#";
59     for(int i = 0; i < s.size(); ++i) {
60         tmp += s[i];
61         tmp += "#";
62     }
63     cout << tmp << endl;
64     string palindrome = manacher(tmp);
65     cout << palindrome << endl;
66     return 0;
67 }

manacher

[2] KMP

判断在字符串 s 中查找模式串 p，返回 p 在 s 中第一个位置下标。

算法讲解我看了 July 的《编程之法》4.4 字符串的查找。

https://blog.csdn.net/v_JULY_v/article/details/7041827

他讲了一个要点，就是next数组的含义，next 数组就是只要将各个前缀和后缀的公共元素的最大长度值右移一位，并且把初值赋值成 -1 即可。

基础题目练习：

(1) leetcode 28 strstr (直接裸的kmp)

 1 class Solution {
 2 public:
 3     int strStr(string haystack, string needle) {
 4         return kmp(haystack, needle);
 5     }
 6     int kmp(string& s, string& p) {
 7         const int n = s.size(), m = p.size();
 8         if (m == 0) {return 0;} //p empty
 9         vector<int> next = getNext(p);
10         int i = 0, j = 0;
11         while (i < n && j < m) {
12             if (j == -1 || s[i] == p[j]) {
13                 ++i, ++j;
14             } else {
15                 j = next[j];
16             }
17         }
18         if (j == m) {
19             return i - j;
20         }
21         return -1;
22     }
23     vector<int> getNext(string& p) {
24         const int n = p.size();
25         vector<int> next(n, 0);
26         next[0] = -1;
27         int j = 0, k = -1;
28         while (j < n - 1) {
29             if (k == -1 || p[j] == p[k]) {
30                 ++k, ++j;
31                 next[j] = p[j] == p[k] ? next[k] : k;
32             } else {
33                 k = next[k];
34             }
35         }
36         return next;
37     }
38 };

View Code

(2) https://hihocoder.com/problemset/problem/1015

题意是找出 S 串中出现模式串 P 的个数。

【内功】基础算法——字符串

[1] Manacher

[2] KMP

【3】求第一个比 N 大的回文数。（字符串处理 + 可以当作数学）

【4】trie 树