一个显然的(O(n^2))算法：考虑从左向右扫描，维护一个栈。
当栈顶的字符和新的字符可以合并时，则把栈顶的字符和新字符合并后把新字符插入栈。
正确性显然。
#include<bits/stdc++.h>
using namespace std;
#define N 200010
int t[30][30],a[N],n,st[N],tp,m,ok[30][30],ans;
char s[N];
int main(){
freopen("arcane.in","r",stdin);
freopen("arcane.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
a[i]=s[i]-'a';
scanf("%d",&m);
for(int i=1;i<=m;i++){
char a[3],b[3],c[3];
scanf("%s%s%s",a,b,c);
if(c[0]!='*'){
t[a[0]-'a'][b[0]-'a']=c[0]-'a';
ok[a[0]-'a'][b[0]-'a']=1;
}
else{
t[a[0]-'a'][b[0]-'a']=-1;
ok[a[0]-'a'][b[0]-'a']=1;
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
st[++tp]=a[j];
while(tp>1&&ok[st[tp-1]][st[tp]]){
int v1=st[tp-1],v2=st[tp];
tp-=2;
if(t[v1][v2]>=0)
st[++tp]=t[v1][v2];
}
if(!tp)
ans++;
}
tp=0;
}
printf("%d",ans);
}
考虑倒着扫描整个字符串，求出以(i)为开头的合法字符串个数。
考虑求出以(i)开头合法的右端点的集合(s)，从小到大排序。
则从(i)开始扫，如果扫到(s_j)，则由栈扫描的过程可知(st_{s_j+1...s_{j+1}})合法。
而且如果(st_{i...j},st_{j+1...k})合法，显然(st_{i...k})合法。
设(f_i,g_i)表示(i)右边第一个位置让(s_{i...f_i-1})合法，(g_i)表示以(i)开头的合法子串个数。
显然(g_i=g_{f_i}+1)
这十分类似括号树。
问题转化成求出(f)。
如果我们从(i+1)推到(i)，栈中会插入一个新字符再插入(st_{i+1...n})。
这需要我们求出(i+1)开始消除成字符(p)，其中(p)和(st_i)能够消除到空且字符串最短。
则问题转化成：对于所有字符(p)，最小右端点(j)，使得(s_{i...j})能够消除成(p)。
令(h_{i,p})表示最小的右端点(+1)，使得(s_{i...h_{i,p}-1})能够消除成(p)。
则考虑枚举字符(t)，，找到一个(e)，使得(t)和(e)能够消除成(p)，且(h_{h_{i,t},e})最小，(h_{i,p}=min(h_{h_{i,t},e}))。
这是因为字符(t)会先跟后缀能够消除成一个字符(c)，且(c)能够和(t)消除的的长度最小的后缀消除。
而且还有以下递推式：(h_{i,p}=min(h_{f_i,p}))
初值(h_{i,s_i}=i+1)，其他(n+2)。
由于保证(c)比(a,b)在字典序下更加靠后，所以可以从(c)字典序小到大递推转移。
时间复杂度(O(n|S|))
#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define int long long
char s[N],t[10];
int le,n,g[N],f[N],h[N][26];
struct no{
char b,c;
};
vector<no>v[N];
signed main(){
freopen("arcane.in","r",stdin);
freopen("arcane.out","w",stdout);
scanf("%s",s+1);
le=strlen(s+1);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%s",t);
a=t[0];
scanf("%s",t);
b=t[0];
scanf("%s",t);
c=t[0];
v[a-'a'].push_back((no){b-'a',c});
}
for(int j=0;j<26;j++)
h[le+1][j]=h[le+2][j]=le+2;
f[le+1]=f[le+2]=le+2;
for(int i=le;i;i--){
f[i]=le+2;
for(int j=0;j<26;j++)
h[i][j]=le+2;
h[i][s[i]-'a']=i+1;
for(int j=0;j<26;j++){
int va=le+2,r=-1;
for(int k=0;k<v[j].size();k++){
no x=v[j][k];
int a=j,b=x.b,c=x.c;
if(va>h[h[i][a]][b]){
va=h[h[i][a]][b];
r=c;
}
}
if(r!=-1){
if(r!='*')
h[i][r-'a']=min(h[i][r-'a'],va);
else
f[i]=min(f[i],va);
}
}
for(int j=0;j<26;j++)
if(f[i]!=le+2)
h[i][j]=min(h[i][j],h[f[i]][j]);
}
for(int i=le-1;i;i--)
if(f[i]!=le+2){
g[i]=g[f[i]]+1;
//printf("%d %d
",i,f[i]);
}
int ans=0;
for(int i=le-1;i;i--)
ans+=g[i];
printf("%lld
",ans);
}