LeetCode总结——字符串相关算法

总结在LeetCode中字符串相关的常用的一些算法

KMP 算法

KMP算法解决的是两个字符串的匹配问题(一个字符串是不是另外一个字符串的子串)

暴力法所需要的时间复杂度是O(n*m),KMP算法能够优化到O(n)。KMP算法的核心是使用一个next数组实现匹配的加速

next数组

最长前缀后缀:一个字符串中所有的前缀和其所有的后缀中最长的相等的长度,比如说“abcabc”的最长前缀后缀为”abc”

给定一个串s的next数组next[],其每一位next[i]表示串s[0…i-1]中最长前缀后缀

使用next数据对字符串匹配进行加速:s1中查找是否有子串s2,如果s1[i]匹配到s2[j]的时候不相等,并且此时next[j]=k,此时不需要重新回到s1[1]继续进行匹配,而是用s2[k]继续和s1[i]进行匹配,依次类推

因为next数组是找到了最长前缀后缀的,所以其能够从最长前缀的匹配跳到最长后缀的匹配,因为中间不可能出现匹配的情况,如果出现匹配那么表示当前next计算的不可能是”最长“前缀后缀。

next数组求法

规定next[0] = -1, 因为其前面没有字符串;next[1] = 0,因为其前面的字符串中只有一个字符,后面的next值的计算取决于前面的next值:

判断当前位置的字符和最长前缀的后一个字符是否相等,如果相等则next[i] = next[i-1] + 1,如果不等再判断最长前缀的最长前缀和其相等不相等,如果还不相等就继续找最长前缀,直到最长前缀长度为0的时候表示没有找到,这个时候next[i] = 0

LeetCode 028

Implement strStr()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
int strStr(string s, string p) {
int len = p.size();
if(len == 0) return 0;
// 生成next数组
vector<int> next(len, 0);
getNext(next, p);
// 两个数组的遍历指针
int i = 0, j = 0;
while(i < s.size() && j < len)
{
if(s[i] == p[j])
{
i++;
j++;
}
else
{
if(j == 0) i++;
// 根据next数组中的信息进行重新指向
else j = next[j];
}
}
return j == len ? i - j : -1;
}
void getNext(vector<int> &next, string p)
{
next[0] = -1;
// k表示最长前缀后缀的长度
int k = -1, i = 0;
// 计算到最后一位
while(i < p.size() - 1)
{
// 相匹配的时候对next数组赋值
if(k == -1 || p[i] == p[k])
next[++i] = ++k;
else
k = next[k];
}
}
};

Manacher 算法

Manacher 算法解决的是字符串中最长的回文子串的问题

暴力法(技巧:中间添加辅助字符)解决这个问题的时间复杂度为O(n^2),Manacher算法能够时间复杂度优化为O(n)

几个概念

  • 回文半径数组,以i为中心的的回文的半径长度
  • 回文右边界,遍历过的回文能够达到的最右的下标
  • 右边界中心位置,回文右边界对应的回文中心点下标

算法过程

和暴力解法一样从左向右扩充判断,有以下几种情况:

  1. 当前位置不在回文右边界里面,暴力扩充
  2. 当前位置在回文右边界里面,其关于右边界中心的对称点的回文区域在左边界里面,其回文半径和其对称点一样
  3. 当前位置在回文右边界里面,其关于右边界中心的对称点的回文左区域超过回文左边界,其回文半径为r-i
  4. 当前位置在回文右边界里面,其关于右边界中心的对称点的回文左区域与回文左边界重合(压线),其回文半径需要在r-i的基础上往后判断

LeetCode 005

Longest Palindromic Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
// Manacher 算法
string longestPalindrome(string s) {
// 添加辅助字符#
string new_s;
new_s.push_back('#');
for(int i = 0; i < s.size(); i++)
{
new_s.push_back(s[i]);
new_s.push_back('#');
}
s = new_s;
int len = s.size();
if(len == 0) return 0;
// 回文半径数组
vector<int> pArr(len, 0);
// C表示回文中心, R表示回文右边界
int C = -1, R = -1;
int maxv = INT_MIN, maxi = 0;
for(int i = 0; i < len; i++)
{
// 在回文右边界里面与否的区分
// 此时pArr表示的是起码不用验的区域
pArr[i] = R > i ? min(pArr[2*C - i], R - i) : 1;
// 区域没有越界
while(i + pArr[i] < len && i - pArr[i] > -1)
{
// 情况1+4 扩充
if(s[i + pArr[i]] == s[i - pArr[i]])
pArr[i]++;
// 情况2+3
else
break;
}
if(i + pArr[i] > R)
{
R = i + pArr[i];
C = i;
}
if(maxv < pArr[i])
{
maxv = pArr[i];
maxi = i;
}
}
string res;
for(int i = maxi - maxv + 1; i <= maxi + maxv - 1; i++)
if(s[i] != '#') res.push_back(s[i]);
return res;
}
};