字符串

Posted on | Post modified: | In |
Words count in article: 925

KMP

​ 在字符串模板匹配中，暴力做法是将模板串依次滑动与目标串比较，每次匹配失败后，向后滑动一位重新与模板串比较。这样模板串前面的子串会重复比较很多次，所以KMP的主要思想是利用模板串已有的信息，在匹配失败后让模板串尽量大步的向后滑动，同时不漏掉可能匹配的情况。

​ 例如：对于模板串abcdabcf，若在最后一个字符f处不匹配，则根据f前面字符串的前缀和后缀的最大相同长度是3，这个长度也是在模板串中前缀后缀匹配的最后一个字符的位置，因此可以直接将它赋值给模版串中当前匹配的位置。KMP中的next数组保存的就是前缀后缀的最大相同长度。根据它可以很快找到下一次开始匹配的位置。

求next数组相当于自己和自己匹配，在匹配的过程中更新next数组（next数组只会往前查找，因此后面的匹配可以像kmp那样直接用next）。next数组中保存的下标是能匹配前缀的后一位，即当前字符与下标前面的前缀匹配（不包括下标所指位置）。如abcdabcd对应的next为[0,0,0,0,1,2,3,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 求next
for(int i = 1, j; i < n; i ++)
{
    j = ne[i - 1];    // j指向上一次匹配到的位置的下一位，也就是需要和当前位置匹配的位置
    while(j && p[i] != p[j]) j = ne[j - 1];  // 判断与当前字符是否匹配，不匹配则依据上一位匹配的前缀回退。
    if(p[i] == p[j]) ++ j;
    ne[i] = j;
}

// kmp
for(int i = 0, j = 0; i < m; i ++)
{
    while(j && s[i] != p[j ])  j = ne[j - 1];// 当模板下一个字符与当前i不匹配时，用next数组找下次匹配的初始位置
    if(s[i] == p[j]) ++ j;
    if(j == n){
        // 匹配成功的逻辑
    }
}

回文串

  • 马拉车算法

回文串即具有对称性质的字符串，利用对称性，我们在求解最长回文串时可利用已求出的回文串的信息，来减少重复的比较操作。

例如 ： abab a babacd

我们在枚举该字符串时，维护一个当前覆盖最远（右）的回文区间，比如枚举到第7位(a)时，最长的回文区间是覆盖到了第9个字符，mid为下标为5的a。它关于mid的对称点是第3位的a，而已它为中心的回文长度是已经计算出来，那么第7位可根据这个信息快速确定一个至少的回文半径。它需要在当前mid的覆盖范围内才有效，因此为

,R是当前覆盖的最远位置， $r[sym_i]$是对称点的回文半径。

用已有信息确定一个较长的回文半径后，再通过中心扩散更新当前字符为中心的最大回文半径。

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
string longestPalindrome(string s) {
    string str = "#";
    for (auto&& c : s) {
        str += c;
        str += "#";
    }

    int n = str.length();
    vector<int> r(n);
    int start = 0, R = 0, len = 0, mid = 0;

    for (int i = 0; i < n; ++ i) {
        if (i < R) {
            int sym_i = 2 * mid - i;
            r[i] = min(R - i, r[sym_i]);
        }

        int left = i - r[i] - 1, right = i + r[i] + 1;
        while (left >= 0 && right < n && str[left] == str[right]) {
            -- left, ++ right, ++ r[i];
        }

        if (i + r[i] > R) {
            R = i + r[i];
            mid = i;
        }

        if (r[i] > len) {
            len = r[i];
            start = (i - r[i] ) / 2;
        }
    }

    return s.substr(start, len);
}