字符串算法

2022-04-09 | 阅读：次

===

Index

字符串哈希
- acwing841
字符串字典树
kmp算法
z函数
ac自动机 -简单版 -强化版
manacher算法
回文自动机
- 每个位置结束的回文串数目
字符串最小表示
lyndon分解
子串分值和
子串唯一字符和
最大波动子字符串
统计子串
有趣子串计数
统计不同回文子序列
字符串排列的最少交换次数

字符串哈希

前缀哈希法：

对于一个长度为n的字符串s来说，我们可以这样定义多项式 Hash 函数：

s = s[1], s[2], ... , s[n]
f(s) = (s[1]*b^(n-1) + s[2]*b^(n-2),+ ... + s[n]*b^0) % M

例如，对于字符串 “xyz”，其哈希函数值为 x*b^2 + y*b + z

设 h[i] 表示 s的前i个字符的哈希值，则，s[i]到s[j]的子串哈希值为 h[j] - h[l-1] * b^(r-l+1)

双哈希模板

using ull = unsigned long long;
struct StrHash{
    const int P1 = 131, P2 = 13331; //or 131
    vector<ull> h1,h2,p1,p2;
    StrHash(){h1={0},h2={0},p1={1},p2={1};}
    StrHash(string s){
        h1={0},h2={0},p1={1},p2={1};
        add(s);
    }
    void add(char c) {
        h1.push_back(h1.back() * P1 + c);
        p1.push_back(p1.back() * P1);
        h2.push_back(h2.back() * P2 + c);
        p2.push_back(p2.back() * P2);
    }
    void add(string s){
        int n = s.size();
        for(int i = 0;i < n; ++i) {
            add(s[i]);
        }
    }
    vector<ull> get(int l, int r) {
        //s[l],...s[r];
        return {h1[r+1]-h1[l]*p1[r-l+1],h2[r+1]-h2[l]*p2[r-l+1]};
    }
};

复杂版模板

string_hash

使用方法

定义哈希字符串

string_hash<string> f(s);

获取s[i…j]的哈希值 [i，j+1) 左闭右开。

f.substring_hash(i, j + 1)

acwing841

acwing 841

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

struct StrHash{
    ...
};
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    string s;
    cin>>s;
    StrHash sh(s);
    while(m--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(sh.get(l1,r1)==sh.get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

模板2

int main(){
    int n,m;
    string s;
    cin>>n>>m>>s;
    long long ans=0;
    string_hash<string> f(s);
    while(m--){
        int l1,l2,r1,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(f.substring_hash(l1-1,r1)==f.substring_hash(l2-1,r2)) puts("Yes");
        else puts("No");
    }
}

字典树

字典树模板

该字典树模板可以用来求解：

给定字符串s，统计trie中多少个字符串等于s
给定字符串s，统计trie中多少个字符串是s的前缀字符串
给定字符串s，统计s是trie中多少个字符串的前缀
给定字符串s，对s的每个前缀串t，统计t是trie中多少个字符串的前缀，并对所有t求和

// 最小字母CH是'a'，字母集大小K是26
template<char CH = 'a', int K = 26>
struct trie {
    struct node {
        array<int, K> child;
        int cnt[2]{0, 0};
        node () { memset(&child[0], -1, K * sizeof(int));}
    };

    vector<node> tr = {node()};

    trie(int tot_len = -1) {
        if (tot_len >= 0) tr.reserve(tot_len + 1);
    }

    int add(const string &s) {
        int p = 0; 
        for (char ch: s) {
            int u = ch - CH;
            if (tr[p].child[u] < 0) {
                tr[p].child[u] = int(tr.size());
                tr.emplace_back();
            }
            p = tr[p].child[u];
            tr[p].cnt[0]++;
        }
        tr[p].cnt[1]++;
        return p;
    }

    // prefix_of_s=1: trie中多少个字符串等于 s (如果count_prefix=1，求多少个字符串是s的前缀)
    // prefix_of_s=0: s是trie中多少个字符串的前缀 (如果count_prefix=1，对s的每个前缀也进行累加)
    int get(const string &s, bool prefix_of_s = 0, bool count_prefix = 0) {
        int p = 0, ans = 0;
        for (char ch: s) {
            if (count_prefix) ans += tr[p].cnt[prefix_of_s];
            p = tr[p].child[ch - CH];
            if (p < 0) break;
        }
        if (p >= 0) ans += tr[p].cnt[prefix_of_s];
        return ans;
    }
};

使用方法

如果 s 中全为小写字母，可以定义为

trie t 者 trie<'a', 26> t

如果既有小写字母又有大写字母，又有数字，共62种字符，可以建立一个字符映射，对每个字符映射为新的字符，再求解。

trie<0, 62> t;
auto get=[&](char c) {
    if (c >='a' && c <= 'z'){
        return c - 'a'; // 0 - 25
    }else if(c >= 'A' && c <= 'Z'){
        return c - 'A' + 26; // 26 - 51
    }
    return c - '0' + 52;  // 52 - 61
};

字符串统计

acwing 835

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，输入的字符串总长度不超过 1e5，字符串仅包含小写英文字母。

#include<bits/stdc++.h>
using namespace std;

// 最小字母CH是'a'，字母集大小K是26
template<char CH = 'a', int K = 26>
struct trie {
    struct node {
        array<int, K> child;
        int cnt[2]{0, 0};
        node () { memset(&child[0], -1, K * sizeof(int));}
    };

    vector<node> tr = {node()};

    trie(int tot_len = -1) {
        if (tot_len >= 0) tr.reserve(tot_len + 1);
    }

    int add(const string &s) {
        int p = 0; 
        for (char ch: s) {
            int u = ch - CH;
            if (tr[p].child[u] < 0) {
                tr[p].child[u] = int(tr.size());
                tr.emplace_back();
            }
            p = tr[p].child[u];
            tr[p].cnt[0]++;
        }
        tr[p].cnt[1]++;
        return p;
    }

    // prefix_of_s=1: trie中多少个字符串等于 s (如果count_prefix=1，求多少个字符串是s的前缀)
    // prefix_of_s=0: s是trie中多少个字符串的前缀 (如果count_prefix=1，对s的每个前缀也进行累加)
    int get(const string &s, bool prefix_of_s = 0, bool count_prefix = 0) {
        int p = 0, ans = 0;
        for (char ch: s) {
            if (count_prefix) ans += tr[p].cnt[prefix_of_s];
            p = tr[p].child[ch - CH];
            if (p < 0) break;
        }
        if (p >= 0) ans += tr[p].cnt[prefix_of_s];
        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    string s, x;
    trie t;
    for (int i = 0; i < n; ++i) {
         cin >> s >> x;
         if (s[0] == 'I') t.add(x);
         else cout<<t.get(x,1,0)<<"\n";
    }
}

字符串的前缀分数和

leetcode周赛311 T4

给你一个长度为 n 的数组 words ，该数组由非空字符串组成, 定义字符串 word 的分数等于以 word 作为前缀的 words[i] 的数目。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数总和 。

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 由小写英文字母组成

// 最小字母CH是'a'，字母集大小K是26
template<char CH = 'a', int K = 26>
struct trie {
    struct node {
        array<int, K> child;
        int cnt[2]{0, 0};
        node () { memset(&child[0], -1, K * sizeof(int));}
    };

    vector<node> tr = {node()};

    trie(int tot_len = -1) {
        if (tot_len >= 0) tr.reserve(tot_len + 1);
    }

    int add(const string &s) {
        int p = 0; 
        for (char ch: s) {
            int u = ch - CH;
            if (tr[p].child[u] < 0) {
                tr[p].child[u] = int(tr.size());
                tr.emplace_back();
            }
            p = tr[p].child[u];
            tr[p].cnt[0]++;
        }
        tr[p].cnt[1]++;
        return p;
    }

    // prefix_of_s=1: trie中多少个字符串等于 s (如果count_prefix=1，求多少个字符串是s的前缀)
    // prefix_of_s=0: s是trie中多少个字符串的前缀 (如果count_prefix=1，对s的每个前缀也进行累加)
    int get(const string &s, bool prefix_of_s = 0, bool count_prefix = 0) {
        int p = 0, ans = 0;
        for (char ch: s) {
            if (count_prefix) ans += tr[p].cnt[prefix_of_s];
            p = tr[p].child[ch - CH];
            if (p < 0) break;
        }
        if (p >= 0) ans += tr[p].cnt[prefix_of_s];
        return ans;
    }
};

class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& a) {
        trie t;
        int n = a.size();
        vector<int> c(n);
        for(auto&x:a) t.add(x);
        for(int i=0;i<n;++i){
            c[i]+=t.get(a[i],0,1);
        }
        return c;
    }
};

字典树统计前缀

洛谷 p8306

给定n个字符串s[1],…s[n],和 q次询问, 每次询问给定一个字符串t，求s[1],…,s[n]中有多少个字符串s 满足 t 是 s的前缀。

输入的字符串只含大小写字母和数字，且不含空串。
1 <= n,q <= 1e5, 输入字符串总长度不超过3e6

#include<bits/stdc++.h>
using namespace std;
// 最小字母CH是'a'，字母集大小K是26
template<char CH = 'a', int K = 26>
struct trie {
    struct node {
        array<int, K> child;
        int cnt[2]{0, 0};
        node () { memset(&child[0], -1, K * sizeof(int));}
    };

    vector<node> tr = {node()};

    trie(int tot_len = -1) {
        if (tot_len >= 0) tr.reserve(tot_len + 1);
    }

    int add(const string &s) {
        int p = 0; 
        for (char ch: s) {
            int u = ch - CH;
            if (tr[p].child[u] < 0) {
                tr[p].child[u] = int(tr.size());
                tr.emplace_back();
            }
            p = tr[p].child[u];
            tr[p].cnt[0]++;
        }
        tr[p].cnt[1]++;
        return p;
    }

    // prefix_of_s=1: trie中多少个字符串等于 s (如果count_prefix=1，求多少个字符串是s的前缀)
    // prefix_of_s=0: s是trie中多少个字符串的前缀 (如果count_prefix=1，对s的每个前缀也进行累加)
    int get(const string &s, bool prefix_of_s = 0, bool count_prefix = 0) {
        int p = 0, ans = 0;
        for (char ch: s) {
            if (count_prefix) ans += tr[p].cnt[prefix_of_s];
            p = tr[p].child[ch - CH];
            if (p < 0) break;
        }
        if (p >= 0) ans += tr[p].cnt[prefix_of_s];
        return ans;
    }
};

void solve() {

    int n, q;
    cin >> n >> q;
    trie<0, 62> t;

    auto get=[&](char c) {
        if(c>='a'&&c<='z'){
            return c-'a';
        }else if(c>='A'&&c<='Z'){
            return c-'A'+26;
        }
        return c-'0' + 52;
    };
    string s;

    for (int i = 0; i < n; ++i) {
        cin >> s;
        for(auto&x:s)x=get(x);
        t.add(s);
    }
    for (int i = 0; i < q; ++i) {
        cin >> s;
        for(auto&x:s)x=get(x);
        cout << t.get(s, 0, 0)<<"\n";
    }
}

int main(){
    int t; cin >> t;
    while(t--){
        solve();
    }
}

kmp算法

acwing 831

给定两个字符串s和t,求s在t中所有出现位置的下标。

vector<int> kmp(string s, string t) {
    int n = s.size(), m = t.size();
    vector<int> nxt(n+1), res;
    for (int i = 1, j = 0; i < n; ++i) {
        while (j && s[i] != s[j]) j = nxt[j - 1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
    for (int i = 0, j = 0; i < m; ++i) {
        while(j && t[i] != s[j]) j = nxt[j - 1];
        if (t[i] == s[j]) {
            j++;
            if (j == n) {
                res.push_back(i - n + 1);
                j = nxt[n - 1];
            }
        }
    }
    return res;
}

z函数

对于长度为n的字符串s，定义函数z[i]表示s和s[i,n-1]（即以s[i]开头的后缀）的最长公共前缀的长度，z被称为s的z函数。

leetcode 2223

class Solution {
public:
    vector<int> z_function(string& s) {
        int n = s.size();
        vector<int> z(n, n);
        for (int i = 1, l = 0, r = 0; i < n; i += 1) {
            if (i <= r and z[i - l] < r - i + 1) z[i] = z[i - l];
            else for (z[i] = max(0, r - i + 1); i + z[i] < n && s[z[i]] == s[i + z[i]]; z[i] += 1);
            if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
        }
        return z;
    }
    long long sumScores(string s) {
        vector<int> z = z_function(s);
        long long c = 0;
        for(auto&x: z) c+=x;
        return c;
    }
};

ac自动机

简单版

给定 n 个模式串 s[i] 和一个文本串 t，求有多少个不同的模式串在文本串里出现过。两个模式串不同当且仅当他们编号不同。

洛谷p3808

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int n;

namespace AC {
int tr[N][26], tot;
int e[N], fail[N];

void insert(char *s) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;  // 如果没有则插入新节点
    u = tr[u][s[i] - 'a'];                              // 搜索下一个节点
  }
  e[u]++;  // 尾为节点 u 的串的个数
}

queue<int> q;

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i]) {
        fail[tr[u][i]] =
            tr[fail[u]][i];  // fail数组：同一字符可以匹配的其他位置
        q.push(tr[u][i]);
      } else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}

int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}
}  // namespace AC

char s[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%s", s + 1), AC::insert(s);
  scanf("%s", s + 1);
  AC::build();
  printf("%d", AC::query(s));
  return 0;
}

强化版

有 N 个由小写字母组成的模式串以及一个文本串 T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 T 中出现的次数最多。

洛谷p2796

#include <bits/stdc++.h>
using namespace std;
const int N = 156, L = 1e6 + 6;

namespace AC {
const int SZ = N * 80;
int tot, tr[SZ][26];
int fail[SZ], idx[SZ], val[SZ];
int cnt[N];  // 记录第 i 个字符串的出现次数

void init() {
  memset(fail, 0, sizeof(fail));
  memset(tr, 0, sizeof(tr));
  memset(val, 0, sizeof(val));
  memset(cnt, 0, sizeof(cnt));
  memset(idx, 0, sizeof(idx));
  tot = 0;
}

void insert(char *s, int id) {  // id 表示原始字符串的编号
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;
    u = tr[u][s[i] - 'a'];  // 转移
  }
  idx[u] = id;  // 以 u 为结尾的字符串编号为 idx[u]
}

queue<int> q;

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i]) {
        fail[tr[u][i]] =
            tr[fail[u]][i];  // fail数组：同一字符可以匹配的其他位置
        q.push(tr[u][i]);
      } else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}

int query(char *t) {  // 返回最大的出现次数
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];
    for (int j = u; j; j = fail[j]) val[j]++;
  }
  for (int i = 0; i <= tot; i++)
    if (idx[i]) res = max(res, val[i]), cnt[idx[i]] = val[i];
  return res;
}
}  // namespace AC

int n;
char s[N][100], t[L];

int main() {
  while (~scanf("%d", &n)) {
    if (n == 0) break;
    AC::init();  // 数组清零
    for (int i = 1; i <= n; i++)
      scanf("%s", s[i] + 1), AC::insert(s[i], i);  // 需要记录该字符串的序号
    AC::build();
    scanf("%s", t + 1);
    int x = AC::query(t);
    printf("%d\n", x);
    for (int i = 1; i <= n; i++)
      if (AC::cnt[i] == x) printf("%s\n", s[i] + 1);
  }
  return 0;
}

manacher算法

给定长度为n的字符串s，找出所有对(i,j)，使得s[i,j]为一个回文串。

对于每个位置 i=0,1,…,n-1,我们找出值d1[i]和d2[i],二者分别表示以位置 i 为中心的长度为奇数和长度为偶数的回文串个数, 换个角度，二者也表示了以位置 i 为中心的最长回文串的半径长度（半径长度 d1[i]，d2[i] 均为从位置 i 到回文串最右端位置包含的字符个数）。

struct Manacher {
    int n;
    vector<int> d1, d2;
    Manacher() {}
    Manacher(const string &s) {
        vector<int> a(s.begin(), s.end());
        build(a);
    }
    Manacher(vector<int> &a) {build(a);}
    void build(vector<int> &s) {
        n = s.size();
        d1.resize(n); d2.resize(n);
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
            while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;
            d1[i] = k--;
            if (i + k > r) l = i - k, r = i + k;
        }
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
            while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++;
            d2[i] = k--;
            if (i + k > r) l = i - k - 1, r = i + k;
        }
    }
    pair<int, int> longest_palin() { //最长回文子串<len, 左边界>
        int mx = 0, l;
        for (int i = 0; i < n; ++i) 
            mx = max({mx, 2 * d1[i] - 1, 2 * d2[i]});
        for (int i = 0; i < n; ++i) {
            if (2 * d1[i] - 1 == mx) { l = i - d1[i] + 1; break; }
            if (2 * d2[i] == mx) { l = i - d2[i]; break;}
        }
        return {mx, l};
    }
    bool is_palin(int l, int r) {   // check s[l..(r-1)] 0 <= l <= r < n
        if ((r - l) % 2 == 0) return d2[(l + r) / 2] >= (r - l) / 2;
        return d1[(l + r) / 2] >= (r - l + 1) / 2;
    }
    // 以2n-1个位置(n个字符和n-1个相邻字符点中间)为回文中心的最长回文子串长度
    vector<int> enum_palin() {
        vector<int> ans(2 * n - 1);
        for (int i = 0, j = 0; i < n; ++i) {
            ans[j++] = d1[i] * 2 - 1;
            if (i < n - 1) ans[j++] = d2[i + 1] * 2;
        }
        return ans;
    }
    vector<int> palin_cnt() { // 每个位置开始的回文串数目,i<=j,s[i..j]是回文
        vector<int> c(n);
        c[0] = -1;
        for (int i = 0; i < n; ++i) {
            c[i + 1 - d1[i]]++, c[i - d2[i]]++;
            if (i + 1 < n) c[i + 1] -= 2;
        }    
        for (int i = 1; i < n; ++i) c[i] += c[i - 1];
        return c;
    }
};

使用方法

s[l..(r-1)] 是否是回文串, 时间 O(1)

Manacher m(s);
bool ok = m.is_palin(l, r);

最长回文子串

lc5 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        Manacher m(s);
        auto [x,y]=m.longest_palin();
        return s.substr(y,x);
    }
};

变成回文串最少在前面添加字符数

geeksforgeeks

给定字符串s，在s前面最少添加多少字符，能让s变成回文串。

1 <= s.size() <= 1e6

分析

假设在s前面添加k个字符能让s变为回文串，那么该k个字符与s长度为k的后缀构成回文串，且s的中间部分也构成回文串。

s = "abacd", k = 2, -> s = "dcabacd"

int minChar(string s){
    int n = s.size();
    Manacher m(s);
    
    for(int i = 0; i < n; ++i) {
        if (m.is_palin(0, n - i)) return i;
    }
    return n;
}

每个位置开始的回文串数目

牛客acm同步赛

给出一个序列 a, 对于i，求满足如下条件的j的数目。

i <= j
a[i],…,a[j] 是一个回文串
1 <= n <= 1e6

分析

manacher算法中的 d1[i]和d2[i],二者分别表示以位置 i 为中心的长度为奇数和长度为偶数的回文串个数，也表示了以位置 i 为中心的最长回文串的半径长度

那么对于每个中心点j，在 [j+1-d1[j], j]之间的每个i，j都满足上述条件，使用差分数组，可以在o(n)时间内求出每个i满足的j的数目，由于长度为偶数和奇数都会将j本身计算一遍，最后结果需要减去1。

vector<int> cal(vector<int>& s) {
    int n = s.size(), sum = 0;
    vector<int> d1(n), d2(n), c(n), res(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k--;
        if (i + k > r) l = i - k, r = i + k;
    }
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++;
        d2[i] = k--;
        if (i + k > r) l = i - k - 1, r = i + k;
    }
    for (int i = 0; i < n; ++i) {
        c[i + 1 - d1[i]]++, c[i + 1]--;
        c[i - d2[i]]++, c[i + 1]--;
    }
    for (int i = 0; i < n; ++i) {
        sum += c[i];
        res[i] = sum - 1;
    }
    return res;
}

模板写法

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    Manacher m(a);
    auto p = m.palin_cnt();
    for (int i= 0;i<n;++i){
        cout<<p[i]<<" \n"[i==n-1];
    }
}

前后缀回文串

CF globalRound 7 D2

字符串s由小写字母组成，求一个最长的回文串t，满足:

t的长度不超过s
存在两个字符串a,b 使得 t=a+b ,其中a是s的前缀字符串，b是s的后缀字符串
1 <= s.size() <= 1e6

分析

t可以表示为 s[1..l]+s[(n-r+1)..n]，首先找到一个最大的k满足， s[1]=s[n],s[2]=s[n-1],...,s[k]=s[n-k+1]，在最优解中，一定满足 min(l,r)=k, 我们只需找到一个最长的回文串w,w是𝑠[(𝑘+1)..(𝑛−𝑘)]的前缀或后缀，那么答案就是 s[1..k]+w+s[(n-k+1)..n]

方法一：manacher

string prefix_suffix_palindrome(string &s) {
    int n = s.size();
    int l = -1, r = n, lmx = 0, rmx = 0;
    while (l + 2 < r && s[l + 1] == s[r - 1]) {
        l++, r--;
    } 
    Manacher m(s);

    for (int i = l + 1; i < r; ++i) {
        if (m.is_palin(l + 1, i + 1)) 
            lmx = max(lmx, i - l);
        if (m.is_palin(i, r)) 
            rmx = max(rmx, r - i);
    }

    string t = lmx > rmx ? s.substr(l + 1, lmx) : s.substr(r - rmx, rmx);

    return s.substr(0, l + 1) + t + s.substr(r ,l + 1);
}

方法二：palindromes_tree

struct palindrome_tree{
    // ...
};
string prefix_suffix_palindrome(string &s) {
    int n = s.size(), l = -1, r = n;
    while (l + 2 < r && s[l + 1] == s[r - 1]) {
        l++, r--;
    } 

    string t1 = s.substr(l + 1, r - l - 1), t2 = t1;
    reverse(t2.begin(), t2.end());
    palindrome_tree<int> p1(t1), p2(t2);

    int lmx = p1[p1.longest_suffix()].len, lpos = p1[p1.longest_suffix()].pos;
    int rmx = p2[p2.longest_suffix()].len, rpos = p2[p2.longest_suffix()].pos;

    string t = lmx > rmx ? t1.substr(lpos, lmx) : t2.substr(rpos, rmx);

    return s.substr(0, l + 1) + t + s.substr(r ,l + 1);
}

每个位置的最长回文串长度

library_checker

长度为n的字符串，有2*n-1个回文中心，(n个字符和n-1个相邻字符的中间)，求每个回文中心的最长回文子串的长度。

1 <= n <= 5e5

int main() {
    
    string s;
    cin >> s;
    Manacher m(s);
    vector<int> ans = m.enum_palin();
    for (int i = 0, n = ans.size(); i < n; ++i) 
        cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

回文自动机

回文自动机（Palindromes_Automaton，PAM），也叫回文树，是高效解决回文问题的算法，能够解决很多Manacher算法解决不了的回文题。可以解决如回文串个数、本质不同回文串个数、前缀0-i内回文串个数、某下标结尾的回文串个数等。

模板

template<typename T, int ALPHABET_SIZE = 26, char CH = 'a'>
struct palindrome_tree {
    // node that represents a palindromic substring
    struct node_t {
        T len, pos, cnt; // 回文子串长度、首次出现位置、出现次数
        T depth, suff;   // suff: node-index of largest palindromic suffix
        T next[ALPHABET_SIZE]; // "A".next['x'] --> "xAx"
    };

    vector<char> _str;    // string of letter ordinals (e.g. 'a' is 0)
    vector<node_t> _nodes;
    T _suff;             // node-index of the current longest palindromic suffix
    long long _total;    // 回文子串总数，可到n*n级别

    palindrome_tree() {_init();}

    palindrome_tree(string &s) {
        _init();
        add_all(s);
    }

    void _init() {
        _str.clear();  _nodes.resize(3);
        _nodes[1].len = -1, _nodes[1].suff = 1;
        _nodes[2].len = 0, _nodes[2].suff = 1;
        _suff = 2, _total = 0;
    }

    template<typename C>
    void reserve_more(C& c, size_t sz) {
        if (c.size() + sz <= c.capacity()) return;
        c.reserve(std::max(c.size() + sz, c.capacity() + c.capacity() / 2));
    }

    T add_all(string &s) {
        size_t len = s.size();
        reserve_more(_str, len), reserve_more(_nodes, len);
        T c = 0;
        for (auto &ch: s) c += add(ch);
        return c;
    }

    T add(char let) {
        let = let - CH;
        _str.push_back(let);
        T i = _find_suffix(_suff, let);
        _suff = _nodes[i].next[let];
        if (_suff != 0) {
            _nodes[_suff].cnt++, _total += _nodes[_suff].depth;
            return 0;
        }
        T suff2 = _find_suffix2(i, let);
        _suff = (T)_nodes.size();
        _nodes.push_back({});
        _nodes[_suff].len = _nodes[i].len + 2;
        _nodes[_suff].pos = (T)_str.size() - _nodes[_suff].len;
        _nodes[_suff].cnt = 1;
        _nodes[_suff].suff = suff2;
        _nodes[_suff].depth = _nodes[suff2].depth + 1;
        _nodes[i].next[let] = _suff;
        _total += _nodes[_suff].depth;
        return 1;
    }

    T _find_suffix2(T i, char let) {
        if (i == 1) return 2;
        i = _find_suffix(_nodes[i].suff, let);
        return _nodes[i].next[let];
    }

    T _find_suffix(T i, char let) {
        T sz = (T)_str.size();
        while (sz < _nodes[i].len + 2 || _str[sz - _nodes[i].len - 2] != let) {
            i = _nodes[i].suff;
        }
        return i;
    }

    // This should be called only once after all elements are added!
    void propagate() {
        for (T i = (T)_nodes.size() - 1; i >= 3; i--) {
            T suff = _nodes[i].suff;
            _nodes[suff].cnt += _nodes[i].cnt;
        }
    }

    // Returns the number of total palindromic substrings, counting their multiplicities.
    long long total() const { return _total;}

    // Returns the number of distinct palindromic substrings, each counted only once.
    T distinct() const { return (T)_nodes.size() - 3;}

    // Returns the index of the node representing the longest palindromic suffix.
    T longest_suffix() const { return _suff;}

    // Returns the <length, index> of longest Palindrome substrings
    array<T, 2> longest_palindrome() const {
        T longest = 0, index = 0;
        for (int i = 3; i < (T)_nodes.size(); ++i) 
            if (_nodes[i].len > longest) 
                longest = _nodes[i].len, index = _nodes[i].pos;
        return {longest, index};
        
    } 

    // Returns the number of nodes.
    T size() const { return (T)_nodes.size();}

    // Accesses node by its index.
    node_t& operator[] (T index) { return _nodes[index];}
};

使用方法

定义一个回文树 palindrome_tree<int> pt(s); 或者 palindrome_tree<int, 26, 'A'> pt(s);
字符串中有多少个回文子字符串 pt.total();
字符串的最长回文子串 auto [max_len, pos] = pt.longest_palindrome()

每个位置结束的回文串数目

洛谷p5496

给定一个字符串 s。保证每个字符为小写字母。对于 s 的每个位置，请求出以该位置结尾的回文子串个数。

这个字符串被进行了加密，除了第一个字符，其他字符都需要通过上一个位置的答案来解密。

具体地，若第 i 个位置的答案是 k，第 i+1 字符读入时的ASCII 码为c，则第 i+1 个字符实际的ASCII 码为 (c-97+k)%26+97。所有字符在加密前后都为小写字母。

struct palindrome_tree{
    //...
};
int main(){
    string s;
    cin >> s;
    palindrome_tree<int> pt;
    int k = 0;
    for(auto&c : s){
        c = (c - 97 + k) % 26 + 97;
        pt.add(c);
        k = pt[pt._suff].depth;
        cout<< k << " ";
    }
}

字符串最小表示

当字符串 s 中可以选定一个位置 i 满足 s[i...n] + s[1...i-1] == T 则称 s 与 T 循环同构.

最小表示

字符串 s 的最小表示为与 s 循环同构的所有字符串中字典序最小的字符串

最小表示的O(n)算法

string min_rep(string s){
    int k = 0, i = 0, j = 1, n = s.size();
    while (k < n && i < n && j < n) {
        if (s[(i + k) % n] == s[(j + k) % n]) k++;
        else {
            s[(i + k) % n] > s[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
            if (i == j) i++;
            k = 0;
        }
    }
    i = min(i, j);
    return s.substr(i)+s.substr(0,i);
}

lyndon分解

Lyndon 串 : 对于字符串 s，如果 s 的字典序严格小于 s 的所有后缀的字典序，我们称 s 是 简单串 或者 Lyndon 串。

例如：a, ab, aab, abb, ababb, abcd 都是简单串。

结论1

当且仅当s的字典序严格小于它的所有非平凡(非空且不同于本身)循环同构串时，s才是简单串。

Lyndon分解：串s的Lyndon分解记为 s=w1w2… wk，其中所有wi为简单串，并且他们的字典序按照非严格单减排序，即

w1 >= w2 >= ..., >= wk。这样的分解存在且唯一。

Duval算法

Duval可以在O(n)时间内求出一个串的Lyndon分解。

vector<string> duval(string const& s) {
  int n = s.size(), i = 0;
  vector<string> factorization;
  while (i < n) {
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j])
        k = i;
      else
        k++;
      j++;
    }
    while (i <= k) {
      factorization.push_back(s.substr(i, j - k));
      i += j - k;
    }
  }
  return factorization;
}

最小表示法

string min_cyclic_string(string s) {
  s += s;
  int n = s.size();
  int i = 0, ans = 0;
  while (i < n / 2) {
    ans = i;
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j])
        k = i;
      else
        k++;
      j++;
    }
    while (i <= k) i += j - k;
  }
  return s.substr(ans, n / 2);
}

子串分值和

子串的分值定义为字符串中不同字符的数量。例如 “abbca” 分值为3，因为其有3个不同字符。

给你一个字符串 s, 返回其所有子字符串的总分值。

leetcode 周赛291 p4

分析

对于一个长度为n的字符串，我们考虑其所有子串的个数，可以考虑以下做法，

考虑第i个字符，它和前面字符加起来长度为x, 和后面字符加起来长度为y，则包含字符i的所有子串数目有 x * y个.

例如对于abcd, 其子串个数为 1*4 + 2*3 + 3*2 + 4*1 ，那么我们考虑每个字符在包含它的所有子串，然后减去重复即可，什么样的是重复的呢？我们从左向右考虑每个字符，那么前面第一个和该字符相同的字符的前缀就是重复计算的，我们减去这段前缀长度即可。

例如 XXXXabcaXXXX 对于第一个a我们可以没有顾虑的统计，加上包含它的所有子串即可，对于第二个a，显然我们统计其前缀时可能包含第一个a，设第一个a的下标为z，上述计算子串的公式在这里就要转化为 (x-z)*y 。

class Solution {
public:
    long long appealSum(string s) {
        long long c = 0, n = s.size();
        vector<long long> p(26, -1);
        for (int i = 0; i < n; ++i) {
            c += (i - p[s[i] - 'a']) * (n - i);
            p[s[i] - 'a'] = i;
        }
        return c;
    }
};

子串唯一字符和

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

由于答案可能非常大，请将结果 mod 10 ^ 9 + 7 后再返回。

lc周赛83 p4

分析

考虑这样一个问题，对于s中任一个字符 s[i] ，s 中有多少个子串只包含一个 s[i]，假设有一段子串是这样的 aXXXXaXXXXXa ，其中x为不等于a的其他字符，只包含中间那个a的所有子串共有 5 * 6 = 30个，其中开始位置可以为 XXXXa中的任一个，结束位置可以为 aXXXXX中的任一个。

最后对于每个字符 c，将计数结果进行累加，就得到了最终的答案。

class Solution {
public:
    int uniqueLetterString(string s) {
        int mod = 1e9 + 7, n = s.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            int j = i - 1, k = i + 1;
            while (j >= 0 && s[j] != s[i]) j--;
            while (k < n && s[k] != s[i]) k++;
            ans = (ans + (i - j) * (k - i)) % mod;
        }
        return ans;
    }
};

最大波动子字符串

双周赛78T4

字符串的波动定义为字符串中出现次数最多的字符与出现次数最少的字符次数之差。

给你一个字符串s，只包含小写字母，求s所有子字符串的最大波动值。

分析

枚举哪个字符是出现最多的（记为 x），哪个字符是出现最少的（记为 y）。把字符串中所有 x 改成 1，所有 y 改成 -1，其它的都改成 0。那么该序列的最大非空子段和就是以 x 为出现最多字符，y 为出现最少字符的答案。

注意x和y必须都出现在子串中，不能吧只有x的子串作为答案，。我们可以用变量 d1 维护 x和y的出现次数之差，初始值为0.

同时用另一个变量 d2 维护在包含y是的x和y出现次数之差，初始为负无穷。因为还没有遇到y。遍历字符串s：

当遇到x时， d1 和 d2 均加1
当遇到y时， d1 减1，d1记录此时的 d1值，若 d1位负，则将其置零。

class Solution {
public:
    int largestVariance(string s) {
        int n = s.size(), ans = 0;
        for (char x = 'a'; x <= 'z'; ++x) {
            for (char y = 'a'; y <= 'z'; ++y) {
                if (x == y) continue;
                int d1 = 0, d2 = -n;
                for (auto c : s) {
                    if (c == x) d1++, d2++;
                    else if (c == y) {
                        d2 = -- d1;
                        d1 = max(d1, 0);
                    }
                    ans = max(ans, d2);
                }
            }
        }
        return ans;
    }
};

统计子串

给定长度为n的01串及整数k，需要回答q个询问。第i个询问为[li,ri],

求s[l,r]中有多少子串，该子串中没有字符出现次数超过k次。

1 <= k <= n <= 1e5
1 <= q <= 1e5
1 <= l <= r <= n

分析

设 l[i] 是最大的下标j，使得 s[i,j] 包含至多k个0和k个1。

对于一个查询 [L,R]。以下标i开始的有效string共有 min(R,l[i]) - i + 1。

所以对于查询[L,R] 的答案为

(l[i]-i+1) + ... + (l[k]-k+1) + (R-(k+1)+1) + ... + (R - R + 1)

其中 k 是满足 l[k] <= R 的最大下标。

我们可以对于每一个R，预处理出对应的k。

时间复杂度 O(n + q)

vector<long long> countSubString(string s, int k, vector<vector<int>> &q) {
    int n = s.size(), m = q.size();
    vector<int> l(n), r(n), cnt(2);
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && cnt[s[j] - '0'] + 1 <= k) cnt[s[j++] - '0']++;
        l[i] = j - 1;
        cnt[s[i] - '0']--;
    }
    cnt = {0, 0};
    for (int i = n - 1, j = n - 1; ~i; --i) {
        while (j >= 0 && cnt[s[j] - '0'] + 1 <= k) cnt[s[j--] - '0']++;
        r[i] = j + 1;
        cnt[s[i] - '0']--;
    }
    vector<long long> p(n + 1), ans(m);
    for (int i = 0; i < n; ++i) 
        p[i + 1] = p[i] + l[i];

    for (int i = 0; i < m; ++i) {
        int x = q[i][0], y = q[i][1], t = r[y] - 1;
        if (x <= t) {
            ans[i] = p[t + 1] - p[x] + 1ll * (y - t) * y;
            ans[i] -= (x + y - 2ll) * (y - x + 1ll) / 2;
        } else {
            ans[i] = (y - x + 2ll) * (y - x + 1ll) / 2;
        }

    }
    return ans;
}

有趣子串计数

字符串x是有趣的，当且仅当它满足下面的条件：

x 包含至少 k 种不同字符
x 中任意字符出现的次数相等

给定字符串 S，请求出它有多少子串是有趣的。

1 <= s.length <= 5000
s 中只包含小写字母

分析

子串s[i,j]是有趣的，只需满足以下条件：

子串包含至少 k 中不同字符
子串中出现次数最多的字符的出现次数与包含的不同字符数乘积等于子串长度

int countSubString(string &s, int k) {
    int n = s.size(), ans = 0;
    for (int i = 0; i < n; ++i) {
        map<int, int> mp;
        int mx = 0, cnt = 0;
        for (int j = i; ~j; --j) {
            mp[s[j]]++;
            mx = max(mx, mp[s[j]]);
            if (mx * (int)(mp.size()) == (i - j + 1) && (int)mp.size() >= k)
                ans++;
        }
    }
}

统计不同回文子序列

leetcode 730

定一个字符串 s，返回 s 中不同的非空回文子序列个数。

1 <= s.length <= 1000
s[i] 仅包含 a,b,c,d

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        int n = s.size(), P = 1e9 + 7;
        vector dp(n, vector<int>(n));
        for (int i = 0; i < n; ++i) 
            dp[i][i] = 1;
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len <= n; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s[l] != s[i]) l++;
                    while (r >= l && s[r] != s[j]) r--;
                    if (l > r) 
                        dp[i][j] = (2 + dp[i + 1][j - 1] * 2) % P;
                    else if (l == r)
                        dp[i][j] = (1 + dp[i + 1][j - 1] * 2) % P;
                    else
                        dp[i][j] = (0LL + dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1] + P) % P;
                } else {
                    dp[i][j] = (0LL + dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + P) % P;
                }
            }
        }
        return dp[0][n - 1];
    }
};

字符串排列的最少交换次数

cf 1430E

给定字符串s和t，t是s的一个排列，每次操作可以交换相邻两个字符，求将s转换为t的最少交换次数。

2 <= n < 2e5

分析

考虑s中每个字符在t中的最终位置，相同的字符在s和t中是不会互相交换的，所以s中的第一个a字符，最终会放到t中的第一个a字符，以此类推，求出s中每个字符在t中的结果位置数组，该数组的逆序对数即位需要交换的次数。

template<class Fun> class y_combinator_result {
    Fun _f;
public:
    template<class T> explicit y_combinator_result(T &&fun): _f(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return _f(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_comb(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
template<typename T, typename F> //i < j,且f(a[i], a[j])为true的数对数目
long long count_pairs(T a, F &&f) {
    T buff(a.size());
    return y_comb([&](auto self, int start, int end) -> long long {
        if (end - start <= 1) return 0;
        int mid = (start + end) / 2, left = start, right = mid, n = 0;
        long long res = self(start, mid) + self(mid, end);
        while (left < mid || right < end)
            if (left < mid && (right == end || f(a[left], a[right]))) {
                buff[n++] = a[left++];
            } else {
                buff[n++] = a[right++], res += left - start;
            }
        copy(buff.begin(), buff.begin() + n, a.begin() + start);
        return res;
    })(0, int(a.size()));
}
 // 顺序对: count_pairs(a, less<int>()); // less_equal<int>()
 // 逆序对: count_pairs(a, greater<int>()); // greater_equal<int>()

long long swapCount(string &s, string &t) {
    int n = s.size();
    map<int,vector<int>> mp;
    for (int i = 0; i < n; ++i) {
        mp[t[i]].push_back(i);
    }
    vector<int> a(n);
    for (int i = n - 1; i >= 0; --i) {
        a[i] = mp[s[i]].back();
        mp[s[i]].pop_back();
    }
    return count_pairs(a,greater<int>());
}

king-yyf

king-yyf

字符串算法

Index

字符串哈希

acwing841

字典树

字典树模板

字符串统计

字符串的前缀分数和

字典树统计前缀

kmp算法

z函数

ac自动机

简单版

强化版

manacher算法

最长回文子串

变成回文串最少在前面添加字符数

每个位置开始的回文串数目

前后缀回文串

每个位置的最长回文串长度

回文自动机

每个位置结束的回文串数目

字符串最小表示

lyndon分解

子串分值和

子串唯一字符和

最大波动子字符串

统计子串

有趣子串计数

统计不同回文子序列

字符串排列的最少交换次数