Strings

  • 子序列 将若干元素提取出来并不改变相对位置形成的序列，不一定连续。
  • 子串 连续的子序列。
  • 后缀（Suffix）从某位置到整个串末尾结束的子串。
  • 前缀（Prefix）从串首开始到某位置结束的子串。
  • 字典序 以第 $i$ 个字符作为第 $i$ 关键字进行大小比较，空字符小于字符集内任何字符。

Pattern Searching

Given a text s[] and a pattern p[], print all occurrences of p[] in s[].

Brute force solution

最坏时间复杂度 $\Theta(mn)$。

1
2
3
4
5
6
7
8
9
10
int i = 0, j = 0;
while (i < s.length()) {
    if (s[i] == T[j]) ++i, ++j;
    else i = i-j+1, j = 0;
    if (j == T.length()) {              // 匹配成功
        printf("[%d-%d] ", i-j, i-1);
        i = i - j + 1;
        j = 0;
    }
}

KMP Algorithm

——Knuth-Morris-Pratt 字符串查找算法

PMT（Partial Match Table，部分匹配表）pmt[i] 表示从 p[0] 往后数，同时从 p[i] 往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。这样，j 就被赋为一个合适的值，即 pmt[j-1]。使用自我匹配求出 pmt。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int pmt[N];
void get_pmt(const string& p) {
    for (int i = 1, j = 0; i < p.length(); ++i) {
        while (j && p[i] != p[j]) j = pmt[j-1];   // 前移j指针 直到成功匹配或移到头为止
        if (p[i] == p[j]) ++j;                    // 当前位匹配成功 j指针右移
        pmt[i] = j;                               // 更新pmt的值
    }
}

void kmp(const string& s, const string& p) {
    for (int i = 0, j = 0; i < s.length(); ++i) {
        while (j && s[i] != p[j]) j = pmt[j-1];   // 前移j指针 直到成功匹配或移到头为止
        if (s[i] == p[j]) ++j;                    // 当前位匹配成功 j指针右移
        if (j == p.length()) {                    // 匹配成功
            printf("[%d-%d] ", i-j+1, i);
            j = pmt[j-1];                         // 初始化
        }
    }
}
void eachT() {
    string s, p; cin >> s >> p;
    get_pmt(p);
    kmp(s, p);
}

Palindrome

Manacher Algorithm

Find the longest substring which is palindrome.

在搜索到 $i$ 时，

  • cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。
  • p[i] 以 $i$ 为中心的最长回文串长度。如果 $i$ 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[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
string manacherInit(string s) { // 形成新的字符串 
    if (s.size() == 0) return "^$";
    string ans = "^";
    for (auto c : s) ans += '#', ans += c;
    ans += "#$";
    return ans;
}

int manacher(string ss) {
    string s = manacherInit(ss);
    vector<int> p(s.size());
    int ans = -1, cc = 0, rr = 0;
    for (int i = 1; i < s.size(); ++i) {
        if (i < rr) p[i] = min(p[2 * cc - i], rr - i);  // p[i]的初始值
        else p[i] = 1;
        while (s[i - p[i]] == s[i + p[i]]) ++p[i];      // 继续扩展回文串
        if (rr < i + p[i]) cc = i, rr = i + p[i];       // 出现右边界更大的回文串
        ans = max(ans, p[i] - 1);                       // 记录答案
    }
    return ans;
}

void eachT() {
    string s;
    cin >> s;
    printf("%d\n", manacher(s));
}