字符串（一）

哈希

Hash是一种单射函数，将各种东西映射成一个整数值。
字符串Hash就是指将字符串映射成一个整数值的方法，通常用于比较字符串是否相等。
定义$H(S)$表示将字符串$S$通过方法$H$映射成的整数值。
Hash并不能保证当$H(S)=H(T)$时$S=T$，当出现$H(S)=H(T),S\not=T$时我们称出现了哈希冲突，在构造Hash方法的时候要尽量避免哈希冲突。

我们常说的Hash字符串通常是指将字符串看成若干进制下的整数，然后将整数对一个比较大的质数取模后的结果作为哈希值，称为多项式取模Hash。
根据生日悖论，模哈中使用的模数$Mod$最好超过Hash检验次数的平方。

常见哈希方法

自然溢出

利用unsigned long long 自然溢出，直接用Hash[i]=Hash[i-1]*p+idx(s[i])
但$2^{64}$本身是一个合数，选择合数作为模数相当于选了很多小模数，若其因子中包含零点就会很容易构造哈希冲突。

单哈希

自己规定模数，Hash[i]=(Hash[i-1]*p+idx(s[i]))%mod
这里mod也为素数，且mod越大哈希冲突率越小
但是单模Hash也有比较容易的方法构造Hash冲突。

双（多）哈希

我们将同一个字符串用不同的模数哈希两（多）次构成一个pair，这样的话就更加保险。
目前没有已知的比较好的方法构造多模哈希冲突。

子串的哈希值

求出一个字符串的哈希值后，其子串的哈希值是可以O(1)求出的。

$$H(S[L,R])=\sum\limits_{i=L}^RS[i]\times B^{R-i}\pmod{Mod}$$

令$F(i)=H(Prefix[i])$
则

$$H(S[L,R])=F(R)-F(L-1)\times B^{R-L+1}$$

KMP

Border

如果字符串$S$的同长度的前缀和后缀完全相同，即$Prefix[i]=Suffix[i]$则称此前缀（后缀）为一个Boader，有时也把Boader的长度简称Boader。
特别地，字符串本身也可以是它的Boader，视具体情况而定。

对于字符串$S$和正整数$p$，如果有$S[i]=S[i-p]$，对于$p<i\le \left|S\right|$成立，则称$p$为字符串$S$的一个周期。
若字符串$\left|S\right|$的周期$p$满足$p|\left|S\right|$，则称$p$为$\left|S\right|$的一个循环节。

重要性质：

• $p$是$S$的周期$\Leftrightarrow\left|S\right|-p$是$S$的Boader
• S的boader的boader也是S的boder
• 若$p,q$均为$S$的周期，则$(p,q)$也为$S$的周期
• 一个串的Boader数量是$O(n)$的，但他们组成了$O(\log n)$个等差数列

next数组

定义$next[i]=Prefix[i]$的最大非平凡Boader，$next[1]=0$。

next的构建

考虑$Prefix[i]$的所有长度大于1的Boader去掉最后一个字母以后，就是$Prefix[i-1]$的Boader。
因此在求解$next[i]$的时候，我们只需要依次检查$next[i-1],next[next[i-1]],…,0$，看看其后面一个字符是否等于$S[i]$。

nt[0] = -1, nt[1] = 0;
for (int i = 2; i <= lens; ++i) {
	nt[i] = nt[i - 1];
	while (nt[i] && s[i] != s[nt[i] + 1])
		nt[i] = nt[nt[i]];
	if (s[i] == s[nt[i] + 1])++nt[i];
}
或
nt[0] = -1;
i = 0, j = -1;
while (i != lens) {
	if (j == -1 || s[i] == s[j])nt[++i] = ++j;
	else j = nt[j];
}

复杂度分析

上面的算法看上去是$O(n^2)$的，实际上它的复杂度是$O(n)$。
考虑势能分析，我们求了$n$次$next$，每次的实际代价为$c_i=1$，设势能$\Phi(D_i)$为第$i$次操作时$Prefix[j]$的Boader数量。
显然$\Phi(D_0)=0$，而$\Phi(D_i)\ge 0$，那么就总复杂度是$\sum c_i+\Phi(D_n)-\Phi(D_0)=n+\Phi(D_n)\le n+n$
因此上面求next的算法的复杂度是$O(2n)$的。
实际上，更通俗的理解是$Prefix[j]$的Boader的增加量一定大于等于减少量，而Boader的增加量不会超过$O(n)$，因此减少量也是$O(n)$的。

匹配

考虑当匹配的过程中出现不匹配的情况时，t串用于匹配的前缀缩短直到能再次与s匹配，然后检查下一个位置，那么实际上再次匹配时是用前一次的Boader来匹配的，所以直接跳next就行了。复杂度分析与求next一模一样，都是$O(n)$。

i = j = 0;
while (i < lens) {
    if (j == -1 || s[i] == t[j]) {
        ++i; ++j;//匹配成功，继续匹配
        if (j == lent) {
            //这里成功匹配了一个完整的模式串
            //进行相应操作
            j = nt[j];//其实这里的nt[j]直接就是0了，从第一个开始配
        }
    }
    else j = nt[j];
}

扩展KMP

其实和KMP的推导差不多，求解的问题是$S$中的每一个后缀与$T$的最长公共前缀。

void EXKMP(char s1[],char s2[]) {
    int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);
    getNext(s2);
    while(s1[i] == s2[i] && i < l2 && i < len)++i;
	extend[0] = i;
    po = 0;
    for(i = 1; i < len; i++) {
        if(nt[i - po]+i < extend[po] + po) //第一种情况，直接可以得到extend[i]的值
            ex[i] = nt[i - po];
        else {
			//第二种情况，要继续匹配才能得到extend[i]的值
            j = extend[po] + po - i;
            if(j < 0)j = 0; //如果i>extend[po]+po则要从头开始匹配
            while(i + j < len && j < l2 && s1[j + i] == s2[j])++j;
			extend[i] = j;
            po = i; //更新po的位置
        }
    }
}

Trie树

Trie树即字典树，用树形结构存储多个字符串，构建方法其实很简单：从根节点开始往下找，如果有当前串的对应字符就走到下个点，否则开新节点，像这样录入所有的字符串即可。

void insert(char *s) {
    int now = root, len = strlen(s);
    for (int i = 0; i < len; ++i)
        if (son[now][s[i]])now = son[now][s[i]];
        else now = son[now][s[i]] = ++tot;
}

可持久化Trie树

与主席树的思想类似，我们可以构造可持久化Trie树，也是考虑结构相同的Trie树可减，合并相同部分节省空间。

void insert(int pre. int &now, char *s) {
    now = ++tot;
    for (int i = 0; i < 26; ++i)
        c[now][i] = c[pre][i];
    sum[now] = sum[pre] + 1;
    if (!*s)return;
    insert(c[pre][*s], c[now][*s], s + 1);
}

AC自动机

KMP只支持单模式串的匹配，而AC自动机支持多模式串匹配。
事实上，AC自动机就相当于将KMP的Border概念扩展到了多模式串上。
AC自动机是一种离线数据结构。

构建

我们将所有的模式串建成一棵Trie树，然后类似于KMP，我们要求fail指针。
fail指针的求法与KMP求next类似，求某个点的节点就从它的父节点开始不断跳fail，直到匹配成功。
复杂度分析依然是势能分析，以fail指针的深度增量为势能，显然总势能是$O(\sum\left|S\right|)$的，所以总复杂度是$O(\sum\left|S\right|)$的。

匹配

至于匹配，类比KMP的匹配，每次匹配失败的时候就去跳fail链，直到匹配成功。而根据fail指针的含义，每个点的fail指针指向的字符串都是其本身的一个后缀，如果某个点代表的字符串匹配成功了，那么代表其向上的整条fail链都出现了一次。因此我们可以先标记每个点匹配成功的次数，然后在fail树上统计答案。

模板

struct ACAM {
    int tot, c[N][26], fail[N], v[N], id[N], ans[N];
    vector<int>to[N];
    void insert(char s[], int x) {
        int n = strlen(s), now = 0;
        for (int i = 0; i < n; ++i) {
            int to = s[i] - 'a';
            if (!c[now][to])c[now][to] = ++tot;
            now = c[now][to];
        }
        id[x] = now;
        ++v[now];
    }
    void getfail() {
        queue<int>q;
        q.push(0);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = 0; i < 26; ++i) {
                if (!c[x][i])continue;
                int y = fail[x];
                while (y && !c[y][i])y = fail[y];
                if (c[y][i] && y != x)fail[c[x][i]] = c[y][i], to[c[y][i]].push_back(c[x][i]);
                else fail[c[x][i]] = 0, to[0].push_back(c[x][i]);
                q.push(c[x][i]);
            }
        }
    }
    void dfs(int x) {
        for (auto y : to[x]) {
            dfs(y);
            ans[x] += ans[y];
        }
    }
    void getans(char s[]) {
        int n = strlen(s), now = 0;
        for (int i = 0; i < n; ++i) {
            int to = s[i] - 'a';
            while (now && !c[now][to])now = fail[now];
            if (c[now][to]) {
                now = c[now][to];
            	++ans[now];
            }
        }
        dfs(0);
    }
}A;

Border Series

这是一个非常重要的性质：虽然长度为$n$的字符串的border可能有$n$个，但是如果我们把这些border按长度排序，那么它们可以构成$O(\log n)$个等差数列。