突然意识到自己字符串啥都不会，只能从头开始学了。
KMP
KMP 是用于快速字符串匹配，具体的说，若已知 \(s1,s2\)，KMP 可以让你找到 \(s1\) 中所有 \(s2\) 出现的位置。KMP 的核心思想是如果失配或者匹配成功之后快速跳到下一个可能匹配成功的结点，以做到 \(\mathcal{O}(|s1|+|s2|)\) 的时间复杂度。
先考虑暴力怎么做？一个非常 naive 的想法是暴力查找从 \(i\) 开始是否可行，但是这样的时间复杂度最劣是 \(\mathcal{O}(|s1|\times| s2|)\) 的，无法通过。
然而注意到，在每次失配后，如果是暴力则会从头开始。然而你完全不用这样：你可以跳到下一个可能的地方匹配。那么，什么叫做可能呢？
这里就需要引入 \(kmp\) 数组了：\(kmp_i\) 表示 \(s2_{1 \dots i}\) 这个前缀中的最长公共前后缀的长度。那么如果当前匹配到了 \(j\)，那么 \(kmp_j\) 就是一种可能的位置。然而，这是为什么呢？
如果当前位置 \(i\) 匹配到了 \(j\)，那么说明 \(s1_{(i-j+1)\dots i}=s2_{1\dots j}\)。又因为 \(s2_{1\dots kmp_i}=s2_{(j-kmp_i+1)\dots j} = s1_{(j-kmp_i+1)\dots j}\)，嗯，看到这个式子就显然发现 \(kmp_i\) 是一种可能的位置了。同理，反证法可以证明这是最大的可能的位置。
（记得配图和文字）。
然后就好办了，对于点 \(i\)，如果此前匹配到了 \(x\)，那么一直 \(x \to kmp_x\) 直到 \(x=0\) 或者 \(s1_i=s2_{x+1}\)。然后如果 \(s1_i=s2_{x+1}\)，那么把 \(x\) 变为 \(x+1\)。
（记得配图和文字和代码）。
然而……\(kmp\) 数组怎么求呢……
实际上，求 \(kmp\) 数组的本身就是一个自己匹配自己的过程。你知道了前面所有前缀的 \(kmp\) 之后，相当于与自己匹配。那么通过类似于上述的过程来解决就可以了。
（记得配图和文字和代码）。
（然后来个总的代码）。
P2375 [NOI2014] 动物园 冷静分析一下，发现题目所给的条件就是要求所有长度小于等于原长一半的公共前后缀的数量。 暴力显然是一个个往下跳。可以倍增优化到 \(\mathcal{O}(T n \log n)\)，听说优化一下常数能过，但是本题有更优秀的 \(\mathcal{O}(Tn)\) 做法。
考虑原来 kmp 的过程，首先预处理出如果长度为 \(i\) 可行，那么贡献是 \(sum_i\)。这样暴力就是跳到第一个小于等于原长一半的位置 \(i\)，然后乘上 \(sum_i+1\) 就可以了。
考虑优化这个跳的过程。具体的说，再做一个 ”KMP“，这个新的 KMP 的意义就是上文的所求的意义。即如果长度大于一半就跳到 \(kmp_i\) 上。然后乘上 \(sum_{p}+1\)。正确性比较显然。具体看代码吧。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int T=read();while(T--)
#define NO puts("NO");
#define YES puts("YES");
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
const int Mod=1e9+7;
const int M=1e6+10;
int n,kmp[M],sum[M],ans;
char s[M];
signed main()
{
WT
{
cin>>s+1;n=strlen(s+1);int now=0,ans=1;sum[1]=1;
for (int i=2;i<=n;i++)
{
while(now>0&&s[i]!=s[now+1])now=kmp[now];
if (s[i]==s[now+1])now++;
kmp[i]=now,sum[i]=sum[now]+1;
}now=0;
for (int i=2;i<=n;i++)
{
while(now>0&&s[i]!=s[now+1])now=kmp[now];
if (s[i]==s[now+1])now++;
while(now*2>i)now=kmp[now];
ans=(ans*(sum[now]+1))%Mod;
}cout<<ans<<endl;
}
return 0;
}
字典树
顾名思义是把所有的字母上树，大概是长成这样子的。
（记得配图）
还是很好理解的。主要用途可能并不是很大，主要还是下面的 AC 自动机作铺垫。
一种特殊的字典树是 01-tire，可以解决许多位运算相关的事情。扔个自己出的题吧P6824 「EZEC-4」可乐然而当时 std 写的不是 01-tire。
AC 自动机
前置知识：KMP，字典树，高超的画图能力和观察能力。
P3808 【模板】AC自动机（简单版） oi-wiki 上的讲解
AC 自动机的思想主要是 fail 指针的构造，与 KMP 类似，fail 指针的用途也是快速跳到下一个可能的位置。当此时失配的时候，跳到失配指针处，这样就不用回溯了。
先举个例子：模式串分别是 \(\texttt{abc},\texttt{abb},\texttt{aacb},\texttt{bc}\)，文本串是 \(\texttt{aacbacabbcc}\)。显然答案是 \(3\)。
首先把模式串放到字典树上，其中绿色的数表示有多少个模式串是以这个结尾的（相信这部分是不需要代码的）：
暴力怎么做？暴力就是是对于每个后缀在树上匹配，然后时间复杂度就爆炸了。
然而，我们完全不用对于每个后缀去匹配。这个时候就需要引入所谓的 fail 指针了。fail 指针的定义：称 \(i\) 匹配失败后继续从 \(j\) 开始匹配，\(j\) 是 \(i\) 的 fail（失配指针）。
然而这样的 \(j\) 有很多，到底应该是哪个呢？实际上，fail 指针的含义是：\(root \to j\) 的路径是 \(root \to i\) 的一段后缀，为了保证能够找到所有的，那么 fail 指针就需要是深度最大的那一个。显然不会有重复的。
那么在上述字典树中，就可以轻松找到他们的 fail 指针（如果没有，则为 \(root\)）。
然而这只是你看出来的，具体应该怎么构造呢。
经过大量的画图可以发现：对于当前的节点 \(now\)，它的儿子节点 \(i\) 的 fail 指针就是他的 fail 指针的儿子节点 \(i\)。
可是，如果没有 \(i\) 这个节点怎么办呢？那么直接令 \(i\) 这个节点为它 fail 指针的儿子节点 \(i\)，这样子就能够保证 fail 指针构造无误。（在上图中不会体现问题，但是在一些情况中会）。
这样就可以用 bfs 解决这个问题了，具体可以看代码：
```cpp void getfail() { queue
首先，直接在字典树上匹配下去，这个时候，他的所有后缀显然也都是可以的，那么每次暴力跳所有 fail 指针，因为只要算一次，标记一下就可以了。
这部分的代码：
int get_AC(string s)
{
int ans=0,now=0,len=s.size();
for (int i=0;i<len;i++)
{
now=t[now].son[s[i]-'a'];
int p=now;
while(p&&t[p].val!=-1)
{
ans+=t[p].val,t[p].val=-1;
p=t[p].fail;
}
}return ans;
}
显然，每个点最多遍历过一次，时间复杂度就是 \(\mathcal{O}(|S|)\)。
代码：
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int T=read();while(T--)
#define NO puts("NO");
#define YES puts("YES");
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
const int M=1e6+10;
int a[M];
string s;
struct tree
{
struct node
{
int son[26],val,fail;
}t[M];int cnt;
void insert(string s)
{
int len=s.size();int now=0;
for (int i=0;i<len;i++)
{
if (!t[now].son[s[i]-'a'])t[now].son[s[i]-'a']=++cnt;
now=t[now].son[s[i]-'a'];
}t[now].val++;
}
void getfail()
{
queue<int>q;
for (int i=0;i<26;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<26;i++)
{
int v=t[now].son[i];
if (v)
t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
int get_AC(string s)
{
int ans=0,now=0,len=s.size();
for (int i=0;i<len;i++)
{
now=t[now].son[s[i]-'a'];
int p=now;
while(p&&t[p].val!=-1)
{
ans+=t[p].val,t[p].val=-1;
p=t[p].fail;
}
}return ans;
}
}T;
signed main()
{
int n;cin>>n;
for (int i=1;i<=n;i++)
{
cin>>s;
T.insert(s);
}T.getfail();
cin>>s;cout<<T.get_AC(s)<<endl;
return 0;
}
P5357 【模板】AC自动机（二次加强版）
加强版和二次加强版貌似没啥区别，而且加强版可能会被暴力草而且要多测要找最大之类的比较麻烦，所以直接快进到二次加强版。
这回让你求的是每个串的出现次数。
最 naive 的暴力就建出 AC 自动机之后暴力跳 fail 指针，但是因为这是要算出现次数，就不能直接把遍历过的打上标记，于是时间复杂度就假了。
然后我们可以思考：每次都暴力跳 fail 指针，有什么可以优化的地方呢？
首先可以发现一个震惊的事实，由于 fail 指针构造时的优越性，每个点都有其 fail 指针除了 \(root\)，而且还不会形成环，这意味着把所有的 fail 指针连起来就是一颗树！
再观察一下这个图，你发现了这个性质了吗？
那么每次跳 fail 指针的过程就是在这颗新的树上把整个 \(root \to u\) 的链的所有节点 \(+1\) 的过程。这样的话，每次就不用暴力去跳了，提前预处理好，然后再 dfs 一遍就可以解决这个问题了！
部分代码：
void get_tree()// 建出 fail 树
{
for (int i=1;i<=cnt;i++)
e[t[i].fail].pb(i);
}
void dfs(int u)// dfs 算出每个点上的树
{
for (int i=0;i<e[u].size();i++)
dfs(e[u][i]),t[u].sz+=t[e[u][i]].sz;
}
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int M=1e6+10;
int n,ans[M],ed[M];
string s[M],ss;
struct tree
{
struct node
{
int son[26],fail,val,sz;
}t[M];int cnt;
vector<int>e[M];
void insert(string s,int p)
{
int now=0,len=s.size();
for (int i=0;i<len;i++)
{
if (!t[now].son[s[i]-'a'])t[now].son[s[i]-'a']=++cnt;
now=t[now].son[s[i]-'a'];
}t[now].val=p;ed[p]=now;
}
void getfail()
{
queue<int>q;
for (int i=0;i<26;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<26;i++)
{
int v=t[now].son[i];
if (v)t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
void get_AC(string s)
{
int now=0,len=s.size();
for (int i=0;i<len;i++)
{
now=t[now].son[s[i]-'a'];
t[now].sz++;
}
}
void get_tree()
{
for (int i=1;i<=cnt;i++)
e[t[i].fail].pb(i);
}
void dfs(int u)
{
for (int i=0;i<e[u].size();i++)
dfs(e[u][i]),t[u].sz+=t[e[u][i]].sz;
}
}T;
signed main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>s[i];
T.insert(s[i],i);
}T.getfail();T.get_tree();
cin>>ss;T.get_AC(ss);
T.dfs(0);for (int i=1;i<=n;i++)
cout<<T.t[ed[i]].sz<<endl;
return 0;
}
这个题大概是 P4824 [USACO15FEB]Censoring S 的强化版，那么我们也沿着上一个题的思路。首先建出 AC 自动机，然后枚举每一位，暴力跳 fail 指针，如果没有遍历到就说明没有以其结尾的字符串，并且把这个 now 入栈。否则，最多只会找到一个满足条件的字符串，设其长度为 \(len\)，那么就需要出栈 \(len-1\) 次，并且让此时的栈顶为新的 now，这样算出 \(p_i\) 表示点 \(i\) 有长度为 \(p_i\) 的以 \(i\) 的结尾的可以匹配的字符串，然后倒序处理一下就好了。
然而每次暴力跳 fail 复杂度是错的。。。具体优化也很简单，像上题一样，建出 fail 树，dfs 一遍预处理出每个节点最后能否遍历到，遍历到的字符串的编号。dfs 过程：
void dfs(int u)
{
for (int i=0;i<e[u].size();i++)
{
int to=e[u][i];
if (t[u].val)t[to].val=t[u].val;
dfs(to);
}
}
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
const int M=1e5+10;
int n,Len[M],st[M],top,p[M];
string s[M],t;
struct tree
{
struct node
{
int son[26],val,fail;
}t[M];int cnt;
vector<int>e[M];
void insert(string s,int p)
{
int now=0,len=s.size();
for (int i=0;i<len;i++)
{
if (!t[now].son[s[i]-'a'])t[now].son[s[i]-'a']=++cnt;
now=t[now].son[s[i]-'a'];
}t[now].val=p;
}
void getfail()
{
queue<int>q;
for (int i=0;i<26;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<26;i++)
{
int v=t[now].son[i];
if (v)t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
void get_tree()
{
for (int i=1;i<=cnt;i++)
e[t[i].fail].pb(i);//,cout<<t[i].fail<<' '<<i<<endl;
// for (int i=1;i<=cnt;i++)cout<<t[i].val<<' ';puts("");
}
void dfs(int u)
{
for (int i=0;i<e[u].size();i++)
{
int to=e[u][i];
if (t[u].val)t[to].val=t[u].val;
dfs(to);
}
}
void get_AC(string s)
{
int len=s.size(),now=0;
for (int i=0;i<len;i++)
{
now=t[now].son[s[i]-'a'];
if (t[now].val)
p[i]=Len[t[now].val],top-=Len[t[now].val]-1,now=st[top];
else st[++top]=now;
}int sum=0;string ans="";
for (int i=len-1;i>=0;i--)
{
sum+=p[i];
if (sum)sum--;
else ans+=s[i];
}for (int i=ans.size()-1;i>=0;i--)
cout<<ans[i];
}
}T;
signed main()
{
cin>>t>>n;
for (int i=1;i<=n;i++)
{
cin>>s[i],Len[i]=s[i].size();
T.insert(s[i],i);
}T.getfail(),T.get_tree(),T.dfs(0);
T.get_AC(t);
return 0;
}
P4052 [JSOI2007]文本生成器
很多时候，AC 自动机只是一个工具，更重要的是看你如何应用它。
这不是废话吗哪个算法不是这样的。
不难想到容斥，算出不包含任何子串的所有串的个数就可以了。
首先建出 AC 自动机，然后考虑 dp。
设 \(dp_{i,j}\) 表示用了 \(i\) 个字母，当前在 AC 自动机上的第 \(j\) 个节点的方案数，那么直接枚举下一个字母转移就可以了。
注意转移的时候，如果一个节点一直跳 fail 指针之后会遇到一个以其结尾的节点（即 val 为 \(1\)），这样子就不能转移了。建出 fail 树之后 dfs 预处理出哪些点不能选就可以了。
int DP()// DP 部分的代码
{
dp[0][0]=1;
for (int i=1;i<=m;i++)
for (int j=0;j<=cnt;j++)
for (int k=0;k<26;k++)
if (!t[t[j].son[k]].val)
dp[i][t[j].son[k]]=(dp[i][t[j].son[k]]+dp[i-1][j])%Mod;
int ans=0;
for (int i=0;i<=cnt;i++)
ans=(ans+dp[m][i])%Mod;
return ans;
}
然后拿 \(26^m\) 减一下就好了。总代码：
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
const int Mod=1e4+7;
const int M=6010;
int n,m,dp[105][M];
string s[M];
struct tree
{
struct node
{
int son[26],val,fail;
}t[M];int cnt;
vector<int>e[M];
void insert(string s)
{
int now=0,len=s.size();
for (int i=0;i<len;i++)
{
if (!t[now].son[s[i]-'A'])t[now].son[s[i]-'A']=++cnt;
now=t[now].son[s[i]-'A'];
}t[now].val=1;
}
void get_fail()
{
queue<int>q;
for (int i=0;i<26;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<26;i++)
{
int v=t[now].son[i];
if (v)t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
void get_tree()
{
for (int i=1;i<=cnt;i++)
e[t[i].fail].pb(i);
}
void dfs(int u)
{
for (int i=0;i<e[u].size();i++)
{
int to=e[u][i];
if (t[u].val)t[to].val=t[u].val;
dfs(to);
}
}
int DP()
{
dp[0][0]=1;
for (int i=1;i<=m;i++)
for (int j=0;j<=cnt;j++)
for (int k=0;k<26;k++)
if (!t[t[j].son[k]].val)
dp[i][t[j].son[k]]=(dp[i][t[j].son[k]]+dp[i-1][j])%Mod;
int ans=0;
for (int i=0;i<=cnt;i++)
ans=(ans+dp[m][i])%Mod;
return ans;
}
}T;
int poww(int a,int b)
{
int res=1;
while(b)
{
if (b&1)res=res*a%Mod;
a=a*a%Mod,b>>=1;
}return res;
}
signed main()
{
n=read(),m=read();
for (int i=1;i<=n;i++)
{
cin>>s[i];
T.insert(s[i]);
}
T.get_fail(),T.get_tree();T.dfs(0);
int ans=(poww(26,m)-T.DP()+Mod)%Mod;
cout<<ans<<endl;
return 0;
}
P3041 [USACO12JAN]Video Game G
很类似上面一个题，在 AC 自动机上 dp 的过程改成取 \(\max\) 就可以了。代码不放了。一句话题解。
P3311 [SDOI2014] 数数
这个题样例没过都能过。
不过只是因为写错了一个小细节。
有点类似于数位 dp 的 AC自动机的题目。
还是按照讨论先建出 fail 树然后 dfs 预处理出以某个节点结尾是否可行，然后 dp 处理出当前在字典树上的 now 之后走任意 \(k\) 步有多少走法。然后按照数位 dp 的套路，一位一位的去枚举，若第 \(i\) 为上的数字为 \(a_i\)，那么先把这位后加上 \(0 - (a_i-1)\) 的情况都算上，然后让这位后加上 \(a_i\)。dp 代码如下：
for (int i=0;i<len;i++)
{
for (int j=0;j<n[i]-'0';j++)
{
int to=t[now].son[j];
ans=(ans+dp[len-i-1][to])%Mod;
}
now=t[now].son[n[i]-'0'];
if (t[now].val)break;
}
注意到 \(n\) 本身并不会被统计进去，而 \(0\) 会反而会被统计进去，所以加上一句 if (!t[now].val)ans=(ans+1)%Mod;ans=(ans-1+Mod)%Mod; 的特判。
然后你发现你 \(80\) 分。原因在这里：你的数是没有前导零的，但是模式串里反而会有。举个例子，\(n=1000,s=012\)，那么数字 \(12\) 不会被统计进去。
那么特判一下第一位为 \(0\) 的情况就可以了，具体实现的时候，枚举第一个不为 \(0\) 的数的位置和数字就可以了。
for (int i=1;i<=9;i++)
for (int k=0;k<len-1;k++)
ans=(ans+dp[k][t[0].son[i]])%Mod;
然后你发现这还不用特判 \(0\) 了。
P2414 [NOI2011] 阿狸的打字机
这个题真是太简单啦，我一眼就秒了！
应该算是 AC 自动机的比较经典的应用吧，u1s1 能独立做出来这个题还是蛮开心的虽然这个题难度不大，但是我的做法貌似略微麻烦（需要树剖），但是我毕竟还是过了不是吗（
暴力显然是把所有字符串加入 AC 自动机然后暴力匹配，然而无论是前者还是后者时间复杂度都会超时，这意味着我们需要优化这两个过程。
第一部分：优化插入的过程。
暴力插显然复杂度是不对的，因为每个字符可能出现在多个字符串中，所有字符串加起来的长度最多能够大概是 \(len^2\) 这个数量级的
然而可以发现，虽然字符串很多，但是大部分都是相同的，这意味着字典树上的点数仍然是 \(len\) 这个数量级的，先不考虑删除的情况，那么两个字符串直接的差距就是新增的那一段，直接在原来 now 的基础上增加新的那一段就可以了。再考虑删除，删除就相当于 now 回到了之前的情况，那么用一个栈存所有的 now，删除的时候出栈并取栈顶就可以了。
这部分的代码：
for (int i=0;i<len;i++)
{
if (s[i]=='P')ed[++tot]=now;
else if (s[i]=='B')now=st[--top];
else
{
if (!t[now].son[s[i]-'a'])t[now].son[s[i]-'a']=++cnt;
now=t[now].son[s[i]-'a'],st[++top]=now;
}
}
第二部分：优化查询过程。
先考虑暴力怎么做：对于当前字符串，暴力跳每个点的 fail 指针，如果有查询字符串的末尾就把答案加一。
建出 fail 树，那么 fail 树上的某个节点的答案就是当前节点被匹配串中每个节点到 \(root\) 的路径中覆盖了当前节点的数量树。那么不难联想到树剖，直接把每个节点的位置到 \(root\) 的路径全部 \(+1\)，然后查询的时候查特定的点就可以了。
然而如果暴力把每个节点的位置到 \(root\) 的路径 \(+1\) 的复杂度也是错的，但是，我们不难想到离线！然后用类似于上面的方法动态更新这个东西就可以了。时间复杂度 \(\mathcal{O}(n\log^2 n)\)。这部分的代码：
for (int i=1;i<=m;i++)
{
int x=read(),y=read();
q[y].pb(mp(x,i));
}top=now=tot=0;
for (int i=0;i<len;i++)
{
if (s[i]=='P')
{
ed[++tot]=now;
for (int j=0;j<q[tot].size();j++)
ans[q[tot][j].y]=G.query(ed[q[tot][j].x]);
}
else if (s[i]=='B')
{
G.update(now,-1);
now=st[--top];
}
else now=t[now].son[s[i]-'a'],st[++top]=now,G.update(now,1);
}
然而实际上，这个东西根本不需要树剖……把这个东西差分一下就能惊奇的发现，求的就是 \(s_x\) 末尾位置的子树和，运用 dfs 序和树状数组就可以得到 \(\mathcal{O}(n\log n)\) 的优秀复杂度，重点是还！非！常！好！写！看来还是我 naive 了啊/kk。代码就不贴了，因为我写烦了。
CF1202E You Are Given Some Strings...
一遇到不那么套路的题就不会了呢……看来自己还是太菜了。
做题的时候思考在优化这个建图的过程，然后就 GG 了。枚举分割的点 \(x\)，如果可以迅速算出 \(s\) 中以 \(x\) 结尾的模式串 \(t\) 的数量，以 \(x+1\) 开始的模式串 \(t\) 的数量，乘起来就可以了。
前面一个问题就是 AC 自动机的经典问题，后面那个也很简单，你不难发现把字符串翻转一下就变成原来那个问题了。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int T=read();while(T--)
#define NO puts("NO");
#define YES puts("YES");
using namespace std;
const int M=2e5+10;
int n;
string s;
struct tree
{
struct node
{
int fail,val,son[26];
}t[M];int cnt,f[M];
vector<int>e[M];
void insert(string s)
{
int len=s.size(),now=0;
for (int i=0;i<len;i++)
{
if (!t[now].son[s[i]-'a'])t[now].son[s[i]-'a']=++cnt;
now=t[now].son[s[i]-'a'];
}t[now].val++;
}
void get_fail()
{
queue<int>q;
for (int i=0;i<26;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<26;i++)
{
int v=t[now].son[i];
if (v)t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
void get_tree()
{
for (int i=1;i<=cnt;i++)
e[t[i].fail].pb(i);
}
void dfs(int u)
{
for (int i=0;i<e[u].size();i++)
{
int to=e[u][i];
t[to].val+=t[u].val;dfs(to);
}
}
void get_ans(string s)
{
int now=0,len=s.size();
for (int i=0;i<len;i++)
{
now=t[now].son[s[i]-'a'];
f[i]=t[now].val;
}
}
}T1,T2;
signed main()
{
cin>>s>>n;int len=s.size();
for (int i=1;i<=n;i++)
{
string t,tt="";
cin>>t;int len=t.size();
T1.insert(t);
for (int i=len-1;i>=0;i--)tt+=t[i];
T2.insert(tt);
}
T1.get_fail(),T1.get_tree();T1.dfs(0);
T2.get_fail(),T2.get_tree();T2.dfs(0);
string ss="";int ans=0;
for (int i=len-1;i>=0;i--)ss+=s[i];
T1.get_ans(s),T2.get_ans(ss);
for (int i=0;i<len-1;i++)
ans+=T1.f[i]*T2.f[len-i-2];//,cout<<i<<' '<<T1.f[i]<<' '<<T2.f[len-i-2]<<endl;
cout<<ans<<endl;
return 0;
}
虽然还是很简单的题，但我就不会做了……看来蒟蒻还要继续努力啊/kk。
P5840 [COCI2015]Divljak
我太菜了/kk。
对于 \(S\) 建出 AC 自动机，那么一个显然的想法是对于每个新加入的 \(t\) 算他对于每个字符串的贡献。
这个东西貌似有点难算，考虑算一个更强的东西：对于字典树上的每一个节点，算出以其为末尾的字符串的答案。这样子看上去更难了，但这意味这是树上连续的若干条链，可以通过树上差分迅速解决。
然而要命的是每个 \(t\) 产生的贡献最多为 \(1\)……
这个时候可以用一个 trick 解决。记录出每次经过的节点并且按照 dfs 序排列之后去重，然后差分的时候把 \(p_i\) 的位置加一 \(LCA_{p_i,p_{i+1}}\) 的位置减一就可以了，不难发现这是对的。
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int T=read();while(T--)
#define NO puts("NO");
#define YES puts("YES");
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
const int M=2e6+10;
struct node
{
int fail,son[26];
}t[M];int cnt;//,f[M];
int n,m,dfn[M],size[M],ti,p[M],ed[M],de[M],pp[M],f[M][23];
vector<int>e[M];
struct BIT
{
int c[M],maxn;
int lowbit(int x){return x&(-x);}
void add(int x,int k)
{
for (int i=x;i<=maxn;i+=lowbit(i))
c[i]+=k;
// cout<<x<<' '<<k<<endl;
}
int ask(int x)
{
int res=0;
for (int i=x;i>=1;i-=lowbit(i))
res+=c[i];
return res;
}
int query(int l,int r){return ask(r)-ask(l-1);}
}T;
void insert(string s,int p)
{
int len=s.size(),now=0;
for (int i=0;i<len;i++)
{
if (!t[now].son[s[i]-'a'])t[now].son[s[i]-'a']=++cnt;
now=t[now].son[s[i]-'a'];
}ed[p]=now;
}
void get_fail()
{
queue<int>q;
for (int i=0;i<26;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<26;i++)
{
int v=t[now].son[i];
if (v)t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
void get_tree()
{
for (int i=1;i<=cnt;i++)
e[t[i].fail].pb(i);//,cout<<t[i].fail<<' '<<i<<endl;
}
void dfs(int u)
{
dfn[u]=++ti,size[u]=1,de[u]=de[t[u].fail]+1;
for (int i=0;i<e[u].size();i++)
{
int to=e[u][i];
dfs(to),size[u]+=size[to];
}
}
bool cmp(int a,int b){return dfn[a]>dfn[b];}
void dp()
{
for (int i=0;i<=cnt;i++)f[i][0]=t[i].fail;
for (int j=1;j<=22;j++)
for (int i=0;i<=cnt;i++)
f[i][j]=f[f[i][j-1]][j-1];
}
int LCA(int x,int y)
{
if (de[x]<de[y])swap(x,y);
for (int i=20;i>=0;i--)
if (de[f[x][i]]>de[y])x=f[x][i];
if (de[x]!=de[y])x=f[x][0];
if (x==y)return x;
for (int i=20;i>=0;i--)
if (f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
signed main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
string s;cin>>s;
insert(s,i);
}T.maxn=cnt+1;
get_fail(),get_tree(),dfs(0);dp();
// for (int i=0;i<=cnt;i++)
// cout<<i<<' '<<dfn[i]<<' '<<size[i]<<endl;
cin>>m;
while(m--)
{
int opt;cin>>opt;
if (opt==1)
{
string s;cin>>s;
int len=s.size(),now=0;
for (int i=0;i<len;i++)
{
now=t[now].son[s[i]-'a'];
p[i+1]=now;
}
sort(p+1,p+1+len,cmp);int top=0;
for (int i=1;i<=len;i++)
if (p[i]!=p[i-1])pp[++top]=p[i];
// cout<<top<<' ';
// for (int i=1;i<=top;i++)cout<<pp[i]<<' ';
for (int i=1;i<=top;i++)
T.add(dfn[pp[i]],1);
for (int i=1;i<top;i++)
T.add(dfn[LCA(pp[i],pp[i+1])],-1);
// puts("");puts("");
}
else
{
int x;cin>>x;
cout<<T.query(dfn[ed[x]],dfn[ed[x]]+size[ed[x]]-1)<<endl;
}
}
return 0;
}
P6125 [JSOI2009]有趣的游戏
建出 fail 树之后，相当于对于给出的字典树，一个点在上随机游走，每次随机走到他的出边（即他的 \(m\) 个儿子）之一（因为建了 fail 树的缘故，所有点的儿子都会指向一个节点，或者是根节点），然后如果走到某个字符串结尾就停止，问最终在哪个字符串上停止的概率。这不就是显然的高斯消元吗，实在是太简单了，我一眼就秒了！
然后你发现你不会做这个东西。原来是这样！普通的高斯消元的方法是设经过点 \(x\) 的概率为 \(f_x\) 然后列方程消元，但是这个题很难这么做……一种更加喵喵喵的做法是设经过点 \(x\) 的期望的次数为 \(f_x\)，那么显然，由于结尾处最多经过一次（没有出边），那么此时的期望就是概率了。此外，与前者相比，期望的次数显然是更加容易求的，具体的，有：
其中，\(P(y\to x)\) 表示点 \(y\) 到点 \(x\) 的几率，\(x=0\) 时候的 \(+1\) 是因为一开始的贡献，然后高斯消元即可。不知道为啥有一个点会输出奇怪的东西，把 \(p=0\) 时设置成 \(0.00001\) 就可以了，暂时不是很懂。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int T=read();while(T--)
#define NO puts("NO");
#define YES puts("YES");
#define debug puts("qwq");
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
const int M=15;
const int N=110;
int n,l,m,ed[M];
string s[M];
double a[N][N],ans[N],p[M],q[M];
struct node
{
int son[26],fail,val;
}t[N];int cnt;
vector<pair<int,double> >e[N];
void insert(string s,int p)
{
int now=0;
for (int i=0;i<l;i++)
{
if (!t[now].son[s[i]-'A'])t[now].son[s[i]-'A']=++cnt;
now=t[now].son[s[i]-'A'];
}ed[p]=now;t[now].val=1;
}
void get_fail()
{
queue<int>q;
for (int i=0;i<m;i++)
if (t[0].son[i])q.push(t[0].son[i]);
while(!q.empty())
{
int now=q.front();q.pop();
for (int i=0;i<m;i++)
{
int v=t[now].son[i];
if (v)t[v].fail=t[t[now].fail].son[i],q.push(v);
else t[now].son[i]=t[t[now].fail].son[i];
}
}
}
void get_edge()
{
for (int i=0;i<=cnt;i++)
if (!t[i].val)
for (int j=0;j<m;j++)
e[t[i].son[j]].pb(mp(i,p[j+1]*1.0/q[j+1]));
}
void guass(int n)
{
// for (int i=1;i<=n;i++)
// {
// for (int j=1;j<=n+1;j++)
// cout<<a[i][j]<<' ';
// puts("");
// }
for (int i=1;i<=n;i++)
{
int p=i;
for (int j=i+1;j<=n;j++)
if (fabs(a[j][i])>fabs(a[p][i]))
p=j;
for (int j=1;j<=n+1;j++)
swap(a[i][j],a[p][j]);
for (int j=n+1;j>=i;j--)a[i][j]/=a[i][i];
for (int j=i+1;j<=n;j++)
for (int k=n+1;k>=i;k--)
a[j][k]-=a[j][i]*a[i][k];
}
// for (int i=1;i<=n;i++){
// for (int j=1;j<=n+1;j++)cout<<a[i][j]<<' ';cout<<endl;}
ans[n]=a[n][n+1];
for (int i=n-1;i>=1;i--)
{
ans[i]=a[i][n+1];
for (int j=i+1;j<=n;j++)
ans[i]-=a[i][j]*ans[j];
}
}
signed main()
{
cin>>n>>l>>m;
for (int i=1;i<=m;i++)
{
cin>>p[i]>>q[i];
if (p[i]==0)p[i]=0.00001;
}
for (int i=1;i<=n;i++)
{
cin>>s[i];
insert(s[i],i);
}
get_fail(),get_edge();//debug
for (int i=0;i<=cnt;i++)
{
a[i+1][i+1]=-1;if (i==0)a[i+1][cnt+2]=-1;
for (int j=0;j<e[i].size();j++)
{
int to=e[i][j].x;double w=e[i][j].y;
a[i+1][to+1]+=w;
}
}guass(cnt+1);
for (int i=1;i<=n;i++)printf("%.2lf\n",max(ans[ed[i]+1],0.0));
return 0;
}
马拉车
咕。
exkmp
咕。
一些综合的字符串题：
显然，\(f(s1,s2)\) 的可能取值只有 \(4\) 种：\(1337,0,1,2\)。不难发现，只要判出有多少个 \(f(s1,s2)=1\)，那么问题便引刃而解。
什么情况下 \(f(s1,s2)\) 会等于 \(1\)？不妨 \(s1 < s2\)，且删去其公共前后缀后，\(s1\) 是有序的，那么 \(f(s1,s2)\) 会等于一。
那么先把所有的 \(s_i\) 按照字典序排序，然后对于每个由相同字符构成（即 \(s_i\) 内部排序后所有字符相等）的集合计算贡献。可以直接枚举每个字符串的贡献。对于一个 \(s_i\)，那么 \(\text{LCP(\)s_{i},s_{i+1}) \dots$ LCP\((s_i,s_n)\)}$ 是单调递减的，并且一共有 \(m\) 个可能的取值。对于每种可能的取值都对应着一段范围 \([L,R]\)，以上可以用暴力求 \(\text{LCP}\) 和单调栈实现，那么考虑对于每种可能的取值计算贡献。对于一种可能的 \(\text{LCP}=x\)，那么可以预处理出 \(s_i\) 以 \(x\) 位置开头的连续最长不减子串 \(s_{i,x \dots y}\)，那么就需要找到 \(s_{L} \dots s_{R}\) 中有多少个字符串 \(s_k\) 满足 \(s_{i,y+1 \dots len}=s_{k,y+1 \dots len}\)。把所有字符串倒着插入字典树后字典树每个节点记录一下所有位置然后二分即可。
时间复杂度 \(\mathcal{O(n\times len \times \log n)}\)。
code。