最长回文子串

给定一个长度为 N 的字符串 S，求它的最长回文子串。

Manacher 算法，时间复杂度 O(n)。

一文弄懂Manacher算法 - 知乎 (zhihu.com)

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
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string new_str(string& ostr) {
  string nstr = "^#";
  int n = ostr.size();
  for (int i = 0; i < n; i++) {
    nstr.push_back(ostr[i]);
    nstr.push_back('#');
  }
  nstr.push_back('$');
  return nstr;
}
int main() {
  string str;
  int id = 1;
  while (true) {
    cin >> str;
    if (str == "END") break;
    str = new_str(str);
    int c = 1, r = 0;
    int n = str.size();
    vector<int> p(n);
    for (int i = 1; i < n; i++) {
      if (i >= c + r) {
        r = 0;
        while (str[i + r + 1] == str[i - r - 1]) r++;
        c = i;
        p[i] = r;
      } else {
        int mr = 2 * c - i;
        if (i + p[mr] < c + r) {
          p[i] = p[mr];
        } else {
          int tr = c + r - i;
          while (str[i + tr + 1] == str[i - tr - 1]) tr++;
          p[i] = tr;
          c = i;
          r = tr;
        }
      }
    }
    cout << "Case " << id << ": " << *max_element(p.begin(), p.end()) << endl;
    id++;
  }
}

KMP模式匹配

在线性时间内判定字符串 s2 是否为字符串 s1 的子串，并求出字符串 s2 在 s1 中各次出现的位置。

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
#include <iostream>
#include <vector>
using namespace std;
int main() {
  string s1, s2;
  cin >> s1 >> s2;
  int n1 = s1.size(), n2 = s2.size();
  s1 = " " + s1, s2 = " " + s2;

  vector<int> next(n2 + 1);
  next[1] = 0;
  for (int i = 2, j = 0; i <= n2; i++) {
    while (j > 0 && s2[i] != s2[j + 1]) j = next[j];
    if (s2[i] == s2[j + 1]) j++;
    next[i] = j;
  }
  for (int i = 1, j = 0; i <= n1; i++) {
    while (j > 0 && (j == n2 || s1[i] != s2[j + 1])) j = next[j];
    if (s1[i] == s2[j + 1]) j++;
    if (j == n2) cout << i - n2 + 1 << endl;
  }
  for (int i = 1; i <= n2; i++) {
    cout << next[i] << " ";
  }
  cout << endl;
}

最小表示法

P1368 【模板】最小表示法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> arr(n << 1);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    arr[i + n] = arr[i];
  }
  int i = 0, j = 1, k;
  while(i < n && j < n) {
    for(k = 0; k < n && arr[i + k] == arr[j + k];k++);
    if(k == n) break;
    if(arr[i + k] < arr[j + k]){
      j = j + k + 1;
      if(i == j) j++;
    } else {
      i = i + k + 1;
      if(i == j) i++;
    }
  }
  int l = min(i, j);
  for(int i = 0;i < n;i++) {
    cout << arr[i + l] << " ";
  }
  cout << endl;
}