字符串

• KMP
• 字符串哈希
• AC自动机
• 字典树（Trie树）

KMP

// 替换掉所有word中的p
// Created by Jiang Yinzuo on 2020/3/22.
//

#include <cstdio>
#include <cstring>

const int MAX= 5000007;
int next[MAX];

void get_next(char *word, int len) {
    next[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if (j != -1 && word[i] != word[j]) {
            j = next[j];
        } else {
            next[++i] = ++j;
        }
    }
}

int pos[MAX];
char p[MAX], word[MAX];
char ans[MAX];

int main() {

    int ans_idx;
    while (~scanf("%s%s", word, p)) {
        int len = strlen(word);
        get_next(word, len);

        int p_len = strlen(p);
        int i = 0, j = 0;
        ans_idx = 0;
        while (i < p_len) {
            ans[ans_idx] = p[i];
            while (j != -1 && p[i] != word[j]) {
                j = next[j];
            }
            ++i;
            ++j;
            pos[ans_idx++] = j;
            if (j == len) {
                ans_idx -= len;
                j = pos[ans_idx - 1];
            }
        }
        ans[ans_idx] = '\0';
        printf("%s\n", ans);
    }
    return 0;
}

利用KMP算法中的get_next()可以求字符串最大回文前缀（cf1326D）

字符串哈希

//
// Created by jiang on 2020/8/14.
// POJ3461 子串匹配

#include <cstdio>
#include <cstring>

unsigned char s[1000002];
unsigned char word[10002];

unsigned long hash_table[1000002];
unsigned long p[1000002];

void pre_hash(const unsigned char *str) {
    hash_table[0] = 0;
    p[0] = 1;
    for (int i = 1; str[i - 1]; ++i) {
        hash_table[i] = hash_table[i - 1] * 31 + str[i - 1];
        p[i] = p[i - 1] * 31;
    }
}

/**
 * 获取子串哈希值
 * @param l
 * @param r
 * @return
 */
inline unsigned long get_hash(int l, int r) {
    return hash_table[r] - hash_table[l - 1] * p[r - l + 1];
}

/**
 * BKDR hash函数
 * @param str
 * @return hashcode
 */
unsigned long hashcode(unsigned char *str) {
    unsigned long hash_value = 0;
    for (; *str; ++str) {
        hash_value = hash_value * 31 + *str;
    }
    return hash_value;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {

        scanf("%s %s", word, s);
        pre_hash(s);

        unsigned long hash_value = hashcode(word);
        int count = 0;
        int n = strlen(reinterpret_cast<const char *>(s));
        int len = strlen(reinterpret_cast<const char *>(word));
        for (int i = 1; i <= n - len + 1; ++i) {
            if (hash_value == get_hash(i, i + len - 1)) {
                ++count;
            }
        }

        printf("%d\n", count);
    }
    return 0;
}

AC自动机

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
struct Tree//字典树 
{
    int fail;//失配指针
    int vis[26];//子节点的位置
    int end;//标记以这个节点结尾的单词编号
} AC[100000];//Trie树
int cnt = 0;//Trie的指针
struct Result {
    int num;
    int pos;

    bool operator<(const Result &b) const {
        if (num != b.num)
            return num > b.num;
        else
            return pos < b.pos;
    }
} Ans[100000];//所有单词的出现次数

string text[100000];

inline void Clean(int x) {
    memset(AC[x].vis, 0, sizeof(AC[x].vis));
    AC[x].fail = 0;
    AC[x].end = 0;
}

void Build(const string &s, int Num) {
    int now = 0;//字典树的当前指针
    for (int i = 0; i < s.length(); ++i)//构造Trie树
    {
        if (AC[now].vis[s[i] - 'a'] == 0)//Trie树没有这个子节点
        {
            AC[now].vis[s[i] - 'a'] = ++cnt;//构造出来
            Clean(cnt);
        }
        now = AC[now].vis[s[i] - 'a'];//向下构造
    }
    AC[now].end = Num;//标记单词结尾
}

//构造fail指针
void get_fail() {
    queue<int> q;//队列
    for (int i = 0; i < 26; ++i)//第二层的fail指针提前处理一下
    {
        if (AC[0].vis[i] != 0) {
            AC[AC[0].vis[i]].fail = 0;//指向根节点
            q.push(AC[0].vis[i]);//压入队列
        }
    }
    //BFS求fail指针
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)//枚举所有子节点
        {
            if (AC[u].vis[i] != 0)//存在这个子节点
            {
                AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
                //子节点的fail指针指向当前节点的fail指针所指向的节点的相同子节点
                q.push(AC[u].vis[i]);//压入队列
            } else//不存在这个子节点
                AC[u].vis[i] = AC[AC[u].fail].vis[i];
            //当前节点的这个子节点指向当前节点fail指针的这个子节点
        }
    }
}

int AC_Query(const string &s)//AC自动机匹配
{
    int l = s.length();
    int now = 0, ans = 0;
    for (int i = 0; i < l; ++i) {
        now = AC[now].vis[s[i] - 'a'];//向下一层
        for (int t = now; t; t = AC[t].fail)//循环求解
            Ans[AC[t].end].num++;
    }
    return ans;
}

int main() {
    int n;
    while (true) {
        cin >> n;
        if (n == 0)break;
        cnt = 0;
        Clean(0);
        for (int i = 1; i <= n; ++i) {
            cin >> text[i];
            Ans[i].num = 0;
            Ans[i].pos = i;
            Build(text[i], i);
        }
        AC[0].fail = 0;//结束标志
        get_fail();//求出失配指针
        cin >> text[0];//文本串
        AC_Query(text[0]);
        sort(&Ans[1], &Ans[n + 1]);
        cout << Ans[1].num << endl;
        cout << text[Ans[1].pos] << endl;
        for (int i = 2; i <= n; ++i) {
            if (Ans[i].num == Ans[i - 1].num)
                cout << text[Ans[i].pos] << endl;
            else
                break;
        }
    }
    return 0;
}

字典树（Trie树）

模板

https://www.acwing.com/problem/content/144/

https://ac.nowcoder.com/acm/contest/4370/B 2019上海区域赛B

// 总共几个字符（连续的），起始字符，输入文本总共有多少字符
template<const int NumCh, const char BaseCh, const int TextTotLen>
struct Trie {
protected:
    int next[TextTotLen][NumCh], idx;
    bool exist[TextTotLen];  // 该结点结尾的字符串是否存在

public:
    /**
     * 插入字符串
     * @param s 待插入的字符串
     */
    void insert(char *s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BaseCh;
            if (!next[p][c])
                next[p][c] = ++idx;  // 如果没有，就添加结点
            p = next[p][c];
        }
        exist[p] = true;
    }

    /**
     * 查找字符串
     * @param s 待查找的字符串
     * @return 是否存在
     */
    bool find(char *s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BaseCh;
            if (!next[p][c])
                return false;
            p = next[p][c];
        }
        return exist[p];
    }
};

template<const int NumCh, const char BaseCh, const int TextTotLen>
struct FindPrefixTrie : public Trie<NumCh, BaseCh, TextTotLen> {
protected:
    int visited_cnt[TextTotLen]{0};
    int existed_cnt[TextTotLen]{0};
public:
    /**
     * 插入字符串
     * @param s 待插入的字符串
     */
    void insert(char *s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BaseCh;
            if (!this->next[p][c])
                this->next[p][c] = ++this->idx;  // 如果没有，就添加结点
            p = this->next[p][c];
        }
        ++existed_cnt[p];
    }

    /**
     * 插入时检查s和Trie中的字符串是否存在前缀关系
     * @return True: 没有前缀；false:s是Trie中的字符串的前缀，或Trie中的字符串是s的前缀
     */
    bool insert_no_prefix(char *s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BaseCh;
            if (!this->next[p][c])
                this->next[p][c] = ++this->idx;
            p = this->next[p][c];
            if (this->exist[p]) {
                return false;  // Trie中某个字符串是s的前缀
            }
            ++visited_cnt[p];
        }
        this->exist[p] = true;
        return this->visited_cnt[p] <= 1;  // 若为false，代表s是Trie中某字符串的前缀
    }

    /**
     * 查找Trie中是否存在字符串s的前缀
     * @param s 待查找的字符串
     * @return 是否存在
     */
    bool find_prefix(char *s) {
        int p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BaseCh;
            if (!this->next[p][c])
                return false;
            p = this->next[p][c];
            if (this->exist[p])
                return true;
        }
        return this->exist[p];
    }

    int prefix_cnt(char *s) {
        int res = 0, p = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - BaseCh;
            if (!this->next[p][c])
                return res;
            p = this->next[p][c];
            res += this->existed_cnt[p];
        }
        return res;
    }
};