AT_tenka1_2016_final_c

好久没写过 AC-Automaton 了。来一发。

有个显然的 dp 为 $dp_i=\max(dp_j+w[j+1,i])$，其中 $w[l,r]$ 表示字串 $[l,r]$ 对应的模式串的价值。时间复杂度大概是 $O(|S|\sum|P_i|)$ 的。显然不能过。

考虑这种有一个文本串，很多模式串匹配的题一般怎么做，容易发现可以用 AC-Automaton 维护。

先建出 AC-Automaton，然后将文本串丢进去匹配，每次根据 $S_i$ 在字典图上移动。到 $u$ 点后，不断跳 $fail$ 指针，每遇到一个 trie 树上的节点，且它代表某一个模式串 $j$ 的结尾，则可以转移 $dp_i=\max(dp_i,dp_{i-len_j}+w_j)$，$len$ 为模式串长度。还有不管这一位的转移 $dp_i=\max(dp_i,dp_{i-1})$。

因为 $\max P_i\le200$，每次跳 $fail$ 至少让深度 $-1$，所以每次跳 $fail$ 最多跳 $200$ 次。时间复杂度即为 $O(|S|\max|P_i|)$。

code：

int n,m,dp[N],ed[N];
char s[N],t[N];
struct AC_Automaton{
	int cur,c[M],l[M],fail[M],tr[M][26];
	void insert(char *str,int k){
		int p=0,len=strlen(str+1);
		rep(i,1,len){
			int x=str[i]-'a';
			if(!tr[p][x]){
				tr[p][x]=++cur;
			}
			p=tr[p][x];
		}
		ed[k]=p,l[p]=len;
	}
	void build(){
		queue<int> q;
		rep(i,0,25){
			if(tr[0][i]){
				q.push(tr[0][i]);
			}
		}
		while(q.size()){
			int u=q.front();
			q.pop();
			rep(i,0,25){
				int &v=tr[u][i];
				if(tr[u][i]){
					fail[v]=tr[fail[u]][i];
					q.push(v);
				}else{
					v=tr[fail[u]][i];
				}
			}
		}
	}
	void solve(){
		int p=0;
		rep(i,1,n){
			int x=s[i]-'a';
			p=tr[p][x];
			int u=p;
			while(u){
				dp[i]=max(dp[i],dp[i-l[u]]+c[u]);
				u=fail[u];
			}
			dp[i]=max(dp[i],dp[i-1]);
		}
	}
}AC;
void Yorushika(){
	scanf("%s%d",s+1,&m);
	n=strlen(s+1);
	rep(i,1,m){
		scanf("%s",t+1);
		AC.insert(t,i);
	}
	rep(i,1,m){
		scanf("%d",&AC.c[ed[i]]);
	}
	AC.build();
	AC.solve();
	printf("%d\n",dp[n]);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}