KMP

$\pi[i]$ 为 $s[0…i]$ 的前缀函数( 最长的相等的真前缀(不能是 $s$ 本身)与真后缀的长度 )

int pi[N];
void getPi(string s) // s 下标从 0 开始
{
    int n = s.size();
    for (int i = 1; i < n; i++) 
    {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
}
vector<int> kmp(string t, string s) // 返回 s 在 t 中的起点位置，pi 数组记得来 s+t+1 的大小  
{
    string cur = s + '#' + t;
    int sz1 = t.size(), sz2 = s.size();
    getPi(cur);
    vector<int> v;
    for (int i = sz2 + 1; i <= sz1 + sz2; i++) 
        if (pi[i] == sz2) v.push_back(i - 2 * sz2);
    return v;
}

前缀函数应用

字符串周期(循环节)

若 $s$ 有长度为 $r$ 的前缀和长度为 $r$ 的后缀相等，则称 $s$ 有长度为 $r(0 \leq r < |s|)$ 的 $border$

$n - \pi[n-1]、n-\pi[\pi[n-1]-1]…$ 是 $s$ 的周期的 $border$ 长度

$n - \pi[n-1]$ 是 $s$ 的最小周期

例如 $abaaa$ 的最小周期是 $abaa $

统计 $s$ 的每个前缀的出现次数

$s$ 的前缀在 $s$ 中的出现次数

vector<int> ans(n + 1);
for (int i = 0; i < n; i++) ans[pi[i]]++;
for (int i = n - 1; i > 0; i--) ans[pi[i - 1]] += ans[i];//长度为 i 的前缀将处于自己后缀的答案转移给处于自己的前缀
for (int i = 0; i <= n; i++) ans[i]++;//前缀本身的答案

$s$ 的前缀在 $t$ 中的出现次数

与上述问题相同，但现在只需关注 $i \geq n+1$ 的 $\pi[i]$ ，也不需要加前缀本身的答案

一个字符串中本质不同的字串个数

1689071226063

扩展kmp

$z[i]$ 为 $s[i,n-1]$ 和 $s$ 的最长公共前缀，$z[0]=0$

#include<bits/stdc++.h>//求字符串 b 的 z 函数, 和 b 与 a 的每个后缀的LCP长度
#define ll long long  //(a + '#' + b) 可求 a 在 b 中的出现位置
using namespace std;

vector<int> getZ(string s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        } else {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

#define int ll
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    string a, b;
    cin >> a >> b;

    auto t = getZ(b);
    t[0] = t.size();
    int ans = 0;
    for(int i = 0; i < t.size(); i++) ans = ans ^ ((i + 1) * (t[i] + 1));
    cout << ans << '\n';

    t = getZ(b + "#" + a);
    ans = 0;
    for(int i = b.size() + 1; i < t.size(); i++) ans = ans ^ ((i - b.size()) * (t[i] + 1));
    cout << ans << '\n';
}

AC自动机

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

struct node{
    int alp[26], end, fail;
    string s;
    int cnt, id;
}tree[150 * 70 + 10];
int tot;

void insert(string s, int id)//注意字母是否是小写，记得build
{
    int p = 0;
    for(int i = 0; i < s.size(); i++)
    {
        int temp = s[i] - 'a';
        if(!tree[p].alp[temp]) tree[p].alp[temp] = ++tot;
        p = tree[p].alp[temp];
    }
    tree[p].end++;
    tree[p].s = s;
    tree[p].id = id;
}

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


void query(string t)
{
    int u = 0;
    for (int i = 0; i < t.size(); i++) 
    {
        u = tree[u].alp[t[i] - 'a'];  // 转移
        for (int j = u; j; j = tree[j].fail)
            tree[j].cnt += tree[j].end;
    }
}

void solve()
{
    int n;
    while(cin >> n, n)
    {
        for(int i = 1; i <= n; i++)
        {
            string s;
            cin >> s;
            insert(s, i);
        }
        build();
        string t;
        cin >> t;
        query(t);
        
        vector<pair<int, pair<int, string>>> v;
        for(int i = 0; i <= tot; i++) if(tree[i].cnt) v.push_back({tree[i].cnt, {-tree[i].id, tree[i].s}});

        sort(v.begin(), v.end(), greater<pair<int, pair<int, string>>>());

        if(v.empty()) cout << 0 << '\n';
        else
        {
            cout << v[0].first << '\n';
            for(auto &[cnt, it] : v) if(cnt == v[0].first) cout << it.second << '\n';
        }

        for(int i = 0; i <= tot; i++)
        {
            for(int j = 0; j < 26; j++) tree[i].alp[j] = 0;
            tree[i].cnt = tree[i].fail = tree[i].end = 0;
        }
        tot = 0;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve(); 
    return 0;
}

#include <bits/stdc++.h>// fail树优化，求每个模式串在文本串中出现了多少次
using namespace std;
const int N = 2e5 + 10;

int ans[N];
struct AC{//注意字母是否是小写，记得build
    struct node{
        int alp[26], fail;
        int cnt;
        vector<int> id;
    }tree[N];
    int tot;
    vector<int> g[N];

    void insert(string s, int id)
    {
        int p = 0;
        for(int i = 0; i < s.size(); i++)
        {
            int temp = s[i] - 'a';
            if(!tree[p].alp[temp]) tree[p].alp[temp] = ++tot;
            p = tree[p].alp[temp];
        }
        tree[p].id.push_back(id);
    }
    void build() 
    {
        queue<int> que;
        for(int i = 0; i < 26; i++) if(tree[0].alp[i]) que.push(tree[0].alp[i]);
        while(que.size()) 
        {
            int u = que.front();
            que.pop();
            for(int i = 0; i < 26; i++) 
            {
                if(tree[u].alp[i]) 
                {
                    tree[tree[u].alp[i]].fail = tree[tree[u].fail].alp[i];  // fail数组：同一字符可以匹配的其他位置
                    que.push(tree[u].alp[i]);
                } 
                else tree[u].alp[i] = tree[tree[u].fail].alp[i];//直接到可匹配处
            }
        }
    }
    void query(string t)
    {
        int u = 0;
        for (int i = 0; i < t.size(); i++) 
        {
            u = tree[u].alp[t[i] - 'a'];// u 在原字典树中可能不存在，但字典树结构已经改变，会直接指向下一个匹配点
            tree[u].cnt++;
        }
    }
    void dfs(int x)//求子树和
    {
        for(auto &to : g[x])
        {
            dfs(to);
            tree[x].cnt += tree[to].cnt;
        }
        for(auto &id : tree[x].id) ans[id] = tree[x].cnt;
    }
    void failTree()
    {
        for(int u = 1; u <= tot; u++) g[tree[u].fail].push_back(u);//对 fail 边建图(一定是树)
        dfs(0);
    }
}AC;

void solve()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        AC.insert(s, i);
    }
    AC.build();
    string t;
    cin >> t;
    AC.query(t);
    AC.failTree();

    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve(); 
    return 0;
}

二维哈希

const int N = 1e3 + 10;
const int p1 = 23333;
const int p2 = 233;
const int mod = 998243453;//不是998244353
int n, m;
string a[N];//原数组
ll h[N][N], pw1[N], pw2[N];

void init_Hash(int n, int m){//将下标从 (1,1) 开始的矩阵 a 进行哈希
	h[0][0] = 0;
	pw1[0] = pw2[0] = 1;
	for(int i = 1; i <= m; i++){
		h[0][i] = 0;
		pw1[i] = pw1[i - 1] * p1 % mod;
	}
	for(int i = 1; i <= n; i++){
		h[i][0] = 0;
		pw2[i] = pw2[i - 1] * p2 % mod;
	}
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			h[i][j] = (h[i][j - 1] * p1 % mod + a[i][j]) % mod;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			h[i][j] = (h[i - 1][j] * p2 % mod + h[i][j]) % mod;
}
ll get_hash(int x, int y, int xx, int yy)//获得左上角坐标为(x,y),右下角坐标为(xx,yy)的hash值
{ 
	int len1 = yy - y + 1;
    int len2 = xx - x + 1;
    ll res = h[xx][yy];
    res = (res - h[xx - len2][yy] * pw2[len2] % mod + mod) % mod;
    res = (res - h[xx][yy - len1] * pw1[len1] % mod + mod) % mod;
    res = (res + h[xx - len2][yy - len1] * pw2[len2] % mod * pw1[len1] % mod) % mod;
    return res;
}

不积跬步，无以至千里！