arcane

一个显然的\(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}\)合法，\(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}\)表示最小的右端点，使得\(s_{i...h_{i,p}-1}\)能够消除成\(p\)。
则考虑枚举字符\(t,e\)，使得\(t\)和\(e\)能够消除成\(p\)，\(h_{i,p}=\min(h_{h_{i,t},e})\)
而且还有以下递推式：\(h_{i,p}=\min(h_{f_i,p})\)
初值\(h_{i,s_i}=i+1\)，其他\(n+1\)。
时间复杂度\(O(n|S|)\)

arcane

原文：https://www.cnblogs.com/ctmlpfs/p/14598336.html