字符串

板子

字符串下标均从1开始

Trie/字典树（HihoCoder 1014）

const int maxcnt = 1000000 + 100;
const int Size = 30;
// maxcnt 为树的节点总数，cnt 为当前节点总数
// 节点下标范围为[1,cnt]，root为1
struct Trie {
    int root, cnt;
    int tree[maxcnt][Size];
    int val[maxcnt];
    int create() {
        ++cnt;
        memset(tree[cnt], 0, sizeof(tree[cnt]));
        val[cnt] = 0;
        return cnt;
    }
    void Init() {
        cnt = 0;
        root = create();
    }
    inline int id(const char &ch) {
        return ch - 'a';
    }
    void add(char *s, int v) {
        int pos = root;
        for(int i = 1; s[i]; ++i) {
            int w = id(s[i]);
            if(tree[pos][w] == 0) {
                tree[pos][w] = create();
            }
            pos = tree[pos][w];
        }
        val[pos] = v;
    }
    int query(char *s) {
        int pos = root;
        for(int i = 1; s[i]; ++i) {
            int w = id(s[i]);
            if(tree[pos][w] == 0) {
                break;
            }
            pos = tree[pos][w];
        }
        return val[pos];
    }
};

KMP（HDU 2087）

const int maxn = 1000 + 100;
char str1[maxn], str2[maxn];
int Next[maxn];
// str1 为长串，str2 为短串，Next为失配数组，maxn为字符串长度
// 字符串下标从1开始
void get_next(char *s) {
    Next[1] = 0;
    int j = 0;
    for(int i = 2; s[i]; ++i) {
        while(j > 0 && s[i] != s[j + 1]) {
            j = Next[j];
        }
        if(s[i] == s[j + 1]) {
            ++j;
        }
        Next[i] = j;
    }
}
int KMP(char *s1, char *s2) {
    int j = 0, ret = 0;
    for(int i = 1; s1[i]; ++i) {
        while(j > 0 && s1[i] != s2[j + 1]) {
            j = Next[j];
        }
        if(s1[i] == s2[j + 1]) {
            ++j;
        }
        if(s2[j + 1] == '\0') {
            ++ret;
            j = Next[j];
        }
    }
    return ret;
}

AC 自动机（HDU 2222）

const int maxn = 50;
const int maxlen = 21;
const int maxcnt = maxn * maxlen;
const int ac_size = 26;
// maxcnt 为节点数量，ac_size 为每个节点的子节点数，遍历所有节点下标范围为 [0, cnt)
// 其中 root = 0，队列下标范围为 [0, tail)
// 添加完字符串后调用 build 函数
// 创建 ac 自动机，insert 函数与 query 函数的形参字符串下标都从 0 开始
struct ac_auto {
    int cnt, root, head, tail;
    int tree[maxcnt][ac_size];
    int fail[maxcnt], que[maxcnt];
    bool flag[maxcnt];
    int create() {
        memset(tree[cnt], -1, sizeof(tree[cnt]));
        flag[cnt] = false;
        ++cnt;
        return cnt - 1;
    }
    void Init() {
        cnt = 0;
        root = create();
    }
    int id(char ch) {
        return ch - 'a';
    }
    void insert(char *str) {
        int pos = root;
        for(int i = 0; str[i]; ++i) {
            int w = id(str[i]);
            if(tree[pos][w] == -1) {
                tree[pos][w] = create();
            }
            pos = tree[pos][w];
        }
        flag[pos] = true;
    }
    void build() {
        fail[root] = root;
        que[0] = root;
        head = tail = 1;
        for(int i = 0; i < ac_size; ++i) {
            if(tree[root][i] == -1) {
                tree[root][i] = root;
            } else {
                fail[tree[root][i]] = root;
                que[tail++] = tree[root][i];
            }
        }
        while(head != tail) {
            int pos = que[head++];
            if(flag[fail[pos]]) {
                flag[pos] = true;
            }
            for(int i = 0; i < ac_size; ++i) {
                if(tree[pos][i] == -1) {
                    tree[pos][i] = tree[fail[pos]][i];
                } else {
                    fail[tree[pos][i]] = tree[fail[pos]][i];
                    que[tail++] = tree[pos][i];
                }
            }
        }
    }
    int query() {}
};

后缀数组

const int maxn = 4 * 50000 + 100;
int sa[maxn], rankk[maxn<<1], hei[maxn];
char str[maxn];
// 所有数组的下标都从1 开始，maxn 为字符串长度
void get_sa_hei(char *s) {
    static int m[maxn], tmp[maxn], w[maxn];
    int len = strlen(s + 1);
    memset(rankk, 0, sizeof(rankk[0]) * (len * 2 + 2));
    for(int i = 0; i <= 255; ++i) w[i] = 0;
    for(int i = 1; i <= len; ++i) ++w[(int)s[i]];
    for(int i = 1; i <= 255; ++i) w[i] += w[i - 1];
    for(int i = len; i > 0; --i) tmp[w[(int)s[i]]--] = i;
    rankk[tmp[1]] = 1;
    for(int i = 2; i <= len; ++i)
        rankk[tmp[i]] = rankk[tmp[i - 1]] + (s[tmp[i]] != s[tmp[i - 1]]);
    for(int k = 1; k <= len; k <<= 1) {
        for(int i = 0; i <= len; ++i) w[i] = 0;
        for(int i = 1; i <= len; ++i) ++w[rankk[i + k]];
        for(int i = 1; i <= len; ++i) w[i] += w[i - 1];
        for(int i = len; i > 0; --i) m[w[rankk[i + k]]--] = i;
        for(int i = 0; i <= len; ++i) w[i] = 0;
        for(int i = 1; i <= len; ++i) ++w[rankk[i]];
        for(int i = 1; i <= len; ++i) w[i] += w[i - 1];
        for(int i = len; i > 0; --i) tmp[w[rankk[m[i]]]--] = m[i];
        m[tmp[1]] = 1;
        for(int i = 2; i <= len; ++i)
            m[tmp[i]] = m[tmp[i - 1]] +
                        (rankk[tmp[i]] != rankk[tmp[i - 1]]
                         || rankk[tmp[i] + k] != rankk[tmp[i - 1] + k]);
        for(int i = 0; i <= len; ++i) rankk[i] = m[i];
    }
    for(int i = 1; i <= len; ++i) sa[rankk[i]] = i;
    for(int i = 1,j = 0; i <= len; ++i) {
        if(rankk[i] == 1) continue;
        for(j? --j: 0; s[sa[rankk[i] - 1] + j] == s[i + j]; ++j);
        hei[rankk[i]] = j;
    }
}

Manacher

const int maxn = 1000 + 100;
char str[maxn];
// str 下标从 1 开始，maxn 为字符串大小
// P 的下标范围为 1 到 n << 1 | 1，每个中心的最长回文长度为 P[i] - 1
// 输入 str 后直接调用 Manacher 返回结果
int Manacher(char *s) {
    int n = strlen(s + 1);
    int len = n << 1 | 1;
    static char str[maxn << 1];
    static int P[maxn << 1];
    str[0] = '$';
    str[1] = '#';
    for(int i = 1; i <= n; ++i) {
        str[i << 1] = s[i];
        str[i << 1 | 1] = '#';
    }
    str[len + 1] = '\0';
    P[1] = 1;
    int ret = 0;
    int id = 1;
    int Max = 1 + P[1];
    for(int i = 2; i <= len; ++i) {
        int j = (i < Max? min(P[2 * id - i], Max - i): 1);
        while(str[i + j] == str[i - j]) {
            ++j;
        }
        P[i] = j;
        ret = max(ret, j - 1);
        if(i + P[i] > Max) {
            id = i;
            Max = i + P[i];
        }
    }
    return ret;
}