一、最长公共子串
题目描述：
字符串s=“heqlloled”，字符串p=“eolold!”。找出两个字符串最长的共有的子字符串。
输入：
acbcbcef
abcbced
输出：
5
bcbce
解决：
dp[i][j]表示s[0,…i]与p[0,…j]区间之间而且以i和j结尾的最长公共子串长度，状态转移方程：
(1)当s[i]==p[j]时，dp[i][j]=dp[i-1][j-1]+1;
(2)当s[i]!=p[j]时，dp[i][j]=0;
代码如下：
1 string LongestCommonSubstring(string s, string p)
2 {
3 int slen = s.size(), plen = p.size();
4 vector<vector<int> > dp(slen + 1, vector<int>(plen + 1, 0));
5
6 //anslen代表公共子串的长度，endpos代表公共子串的结束位置
7 int anslen = 0, endpos = -1;
8 for (int i = 1; i <= slen; i++)
9 {
10 for (int j = 1; j <= plen; j++)
11 {
12 if (s[i - 1] == p[j - 1])
13 {
14 dp[i][j] = dp[i - 1][j - 1] + 1;
15 if (dp[i][j] > anslen)
16 {
17 anslen = dp[i][j];
18 endpos = i - 1;
19 }
20 }
21 else //两个字符不相等的时候，说明以s[i-1]和p[j-1]结尾的公共子串长度为0
22 {
23 dp[i][j] = 0;
24 }
25 }
26 }
27
28 //获取公共子串
29 string ansstr = s.substr(endpos - anslen + 1, anslen);
30 return ansstr;
31 }
二、最长公共子序列
题目描述：
字符串s=“heqlloled”，字符串p=“eolold!”。输出最长公共子序列。
输入：
abcde
ace
输出：
3
ace
解决：
dp[i][j]表示s[0,…i]与p[0,…j]的最长公共子序列长度。
状态转移方程：
(1) 当s[i]==p[j]时，dp[i][j] = dp[i-1][j-1] + 1;
(2) 当s[i]!=p[j]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
代码如下：
1 string longestCommonSubsequence(string s, string p)
2 {
3 int slen = s.size(), plen = p.size();
4 vector<vector<int> > dp(slen + 1, vector<int>(plen + 1, 0));
5
6
7 for (int i = 1; i <= slen; i++)
8 {
9 for (int j = 1; j <= plen; j++)
10 {
11 if (s[i - 1] == p[j - 1])
12 {
13 dp[i][j] = dp[i - 1][j - 1] + 1;
14 }
15 else //两个字符不相等的时候，说明以s[i-1]和p[j-1]结尾的公共子串长度为0
16 {
17 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
18 }
19 }
20 }
21
22 int index1 = slen, index2 = plen;
23 string ans;
24 while (index1 > 0 && index2 > 0)
25 {
26 if (s[index1 - 1] == p[index2 - 1])
27 {
28 ans.push_back(s[index1 - 1]);
29 index1--;
30 }
31 else
32 {
33 if (dp[index1][index2 - 1] > dp[index1 - 1][index2])
34 index2--;// 说明相同的字符在行这边，下次遍历的时候应该是同一行，列向前退一格，所以index2--
35 else
36 index1--;
37 }
38 }
39
40 reverse(ans.begin(), ans.end());
41 return ans;
42 }
三、寻找目标子串
题目链接：https://leetcode-cn.com/problems/implement-strstr/
在一个字符串中寻找是否包含目标字符串，实现这个要求并不难，遍历文本的每个字符串，如果和目标字符串的第一个匹配，就把匹配的字符后移一位继续对比，直到不匹配，然后将文本的指针后移一位，继续对比即可。但是这样的暴力匹配最坏情况的时间复杂度为O（n*m），而KMP算法可以将其复杂度降低到O（n+m），减少重复对比次数。
代码如下：
1 void getNext(string str, vector<int> & next)
2 {
3 //这里必须是减1
4 int len = str.size() - 1;
5 int i = 0, k = -1;
6 next[0] = -1;
7 while (i < len && k < len)
8 {
9 if (k == -1 || str[i] == str[k])
10 {
11 i++;
12 k++;
13 next[i] = k;
14
15 /*
16 i++;
17 k++;
18 if (str[i] == str[k])
19 next[i] = next[k];
20 else
21 next[i] = k;
22 */
23 }
24 else
25 {
26 k = next[k];
27 }
28 }
29 }
30
31
32 int strStr(string source, string target)
33 {
34 int slen = source.size(), tlen = target.size();
35
36 //特殊情况处理
37 if (tlen == 0)
38 return 0;
39
40 if (slen == 0)
41 return -1;
42
43 //获取next数组
44 vector<int> next(tlen, 0);
45 getNext(target, next);
46 int i = 0, j = 0;
47 while (i < slen && j < tlen)
48 {
49 if (j == -1 || source[i] == target[j])
50 {
51 i++;
52 j++;
53 }
54 else
55 {
56 j = next[j];
57 }
58 }
59 if (j >= tlen)
60 {
61 return i - tlen; //返回起始位置
62 }
63 else
64 {
65 return -1; //不存在
66 }
67 }
四、最长回文子串
题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
题目描述：给你一个字符串 s，找到 s 中最长的回文子串。
解法1：动态规划：对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 extrm{``ababa''}“ababa”，如果我们已经知道 extrm{``bab''}“bab” 是回文串，那么 extrm{``ababa''}“ababa” 一定是回文串，这是因为它的首尾两个字母都是 extrm{``a''}“a”。
dp[i][j]代表从i到j的子串是否为回文串，如果s[i] == s[j] 并且j - i == 1或者dp[i+1][j-1]为true，那么dp[i][j] = true;时间复杂度和空间复杂度分别为O(n^2)和O(n^2)。
代码如下：
1 string longestPalindrome(string s)
2 {
3 int len = s.size();
4 vector<vector<bool> > dp(len, vector<bool>(len, false));
5 //初始化
6 for (int i = 0; i < len; i++)
7 dp[i][i] = true;
8
9 //结果标记
10 int anslen = 0, beginpos = 0, endpos = 0;
11
12 for (int i = len - 2; i >= 0; i--)
13 {
14 for (int j = i + 1; j < len; j++)
15 {
16 if (s[i] == s[j] && (j - i == 1 || dp[i + 1][j - 1]))
17 {
18 dp[i][j] = true;
19 if (j - i + 1 > anslen)
20 {
21 anslen = j - i + 1;
22 endpos = j;
23 beginpos = i;
24 }
25 }
26 }
27 }
28
29 string ansstr = s.substr(beginpos, endpos - beginpos + 1);
30
31 return ansstr;
32 }
解法2：中心扩展算法：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。
代码如下：
1 int helper(string s, int left, int right)
2 {
3 while (left >= 0 && right < s.size() && s[left] == s[right])
4 {
5 left--;
6 right++;
7 }
8
9 return right - left - 1;
10 }
11
12
13
14 string longestPalindrome(string s)
15 {
16 int len = s.size();
17
18 int beginpos = 0, endpos = 0, anslen = 0;
19 for (int i = 0; i < len; i++)
20 {
21 int odd_len = helper(s, i, i);
22 int even_len = helper(s, i, i + 1);
23 int tlen = max(odd_len, even_len);
24 if (tlen > anslen)
25 {
26 anslen = tlen;
27 beginpos = i - (tlen - 1) / 2;
28 endpos = i + tlen / 2;
29 }
30 }
31
32 string ansstr = s.substr(beginpos, anslen);
33 return ansstr;
34 }
五、最长重复子串
题目链接：
https://leetcode-cn.com/problems/longest-duplicate-substring/
题目描述：
给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）
解决：二分+字符串哈希
代码如下：
1 const int maxlen = 100000 + 50;
2 typedef unsigned long long ULL;
3 int base = 13331;
4 int f[maxlen], h[maxlen];
5
6 ULL getKey(int l, int r)
7 {
8 return l == 0 ? h[r] : h[r] - h[l - 1] * f[r - l + 1;
9 }
10
11
12 string Check(int mid, string & s)
13 {
14 unordered_map<ULL, bool> mp;
15 int len = s.size();
16 string cur;
17 for (int i = 0; i < len; i++)
18 {
19 if (i + mid - 1 < len)
20 {
21 ULL key = getKey(i, i + mid - 1);
22 if (mp.count(key))
23 {
24 cur = s.substr(i, mid);
25 break;
26 }
27 mp[key] = true;
28 }
29 }
30 return cur;
31 }
32
33
34 string longestDupSubstring(string s)
35 {
36 int len = s.size();
37
38 //预处理哈希值
39 f[0] = 1;
40 for (int i = 0; i < len; i++)
41 {
42 if (i == 0)
43 h[i] = s[i];
44 else
45 {
46 h[i] = h[i - 1] * base + s[i];
47 f[i] = f[i - 1] * base;
48 }
49 }
50
51 string ans;
52 int left = 0, right = len - 1;
53 while (left < right)
54 {
55 int mid = (left + right + 1) / 2;
56 string cur = Check(mid, s);
57 if (cur.size() > ans.size())
58 {
59 ans = cur;
60 left = mid;
61 }
62 else
63 {
64 right = mid - 1;
65 }
66 }
67
68 return ans;
69 }
六、最长不含重复字符的子串
题目链接：
https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
题目描述：
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
解决：双指针+滑动窗口
代码如下：
1 int lengthOfLongestSubstring(string s)
2 {
3 int len = s.size();
4 if (!len)
5 return 0;
6 int left = 0, right = 0, ans = 0;
7 unordered_map<char, int> mp;
8 while (right < len)
9 {
10 char ch = s[right];
11 mp[ch]++;
12 while (mp[ch] > 1)
13 {
14 mp[s[left]]--;
15 left++;
16 }
17 ans = max(ans, right - left + 1);
18 right++;
19 }
20 return ans;
21 }
七、最长递增子序列
题目链接：
https://leetcode-cn.com/problems/longest-increasing-subsequence/
题目描述：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解决：动态规划
代码如下：
1 int lengthOfLIS(vector<int>& nums) {
2 int len = nums.size();
3 vector<int> dp(len + 1, 1);
4 dp[0] = 0;
5 int maxlen = 0;
6 for (int i = 1; i <= len; i++) {
7 for (int j = 1; j < i; j++) {
8 if (nums[i - 1] > nums[j - 1])
9 dp[i] = max(dp[i], dp[j] + 1);
10 }
11 maxlen = max(maxlen, dp[i]);
12 }
13
14 //输出子序列
15 int sublen = maxlen;
16 vector<int> sublis(sublen, 0);
17 int index = len;
18 for (; index > 0; index--)
19 {
20 if (dp[index] == sublen)
21 break;
22 }
23 sublis[--sublen] = nums[index - 1];
24 for (int i = index - 1; i > 0; i--)
25 {
26 if (nums[i - 1] < nums[index - 1] && dp[i] == dp[index] - 1)
27 {
28 sublis[--sublen] = nums[i - 1];
29 index = i;
30 }
31 }
32
33 for (int i = 0; i < maxlen; i++)
34 cout << sublis[i] << " ";
35
36 return maxlen;
37 }
八、参考文章
https://blog.csdn.net/s448312891/article/details/80318746