[洛谷 2292][HNOI2004] L语言【AC自动机+DP】

• 2018-02-27
• 0
• 0

Problem:

题目描述

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。

例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的，因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解，而且是在字典D下能够被理解的最长的前缀。

给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。并给出其在字典D下能够被理解的最长前缀的位置。

输入输出格式

输入格式：

输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。之后的n行每行描述一个单词，再之后的m行每行描述一段文章。

其中1<=n, m<=20，每个单词长度不超过10，每段文章长度不超过1M。

输出格式：

对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。

输入输出样例

4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

14  （整段文章’whatisyourname’都能被理解）
6  （前缀’whatis’能够被理解）
0  （没有任何前缀能够被理解）

Solution:

本题是一道与字符串有关的 DP 题。

我们发现，直接枚举转移复杂度达到 O(mL_T*nL_P) = O(20*10⁶*20*10) = O(4*10⁹)，TLE。

而复杂度瓶颈是字符串匹配，我们可以考虑对于字典中的单词建立 AC 自动机。

AC 自动机在询问时会从前到后找到所有出现在文本中的模式串及其位置，同步 DP 并记录最右的匹配点即可，这样就可以将时间复杂度降至 O(mL_T) = O(20*10⁶) = O(2*10⁷)，可以 AC。

Code: O(mL_T), 其中L_T为文本均长 [4062K, 172MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, m, Plen[22], Tlen;
char P[22][12], T[1050000];
bool dp[1050000];

struct Aho_Corasick_Automaton{
	int trie[202][26], fail[202], id[202], cnt[202], topp;
	int q[202], fr, re;
	
	inline void insert(char *str, int len, int str_id){
		int cur = 0;
		for(register int i = 0; i < len; i++){
			int v = str[i] - 'a';
			if(!trie[cur][v]) trie[cur][v] = ++topp;
			cur = trie[cur][v];
		}
		id[cur] = str_id;  // Only consider one of repeated strings 
	}
	
	inline void build_fail(){
		for(register int i = 0; i < 26; i++) if(trie[0][i]) fail[trie[0][i]] = 0, q[re++] = trie[0][i];
		while(fr != re){
			int u = q[fr++];
			for(register int i = 0; i < 26; i++)
				if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], q[re++] = trie[u][i];
				else trie[u][i] = trie[fail[u]][i];
		}
	}
	
	inline int match_dp(char *str, int len){
		int cur = 0, mx = 0;
		memset(dp, 0, sizeof(dp)), dp[0] = 1;
		for(register int i = 1; i <= len; i++){
			cur = trie[cur][str[i - 1] - 'a'];
			for(register int j = cur; j; j = fail[j])
				if(id[j] && dp[i - Plen[id[j]]]) dp[i] = 1, mx = i;
		}
		return mx;
	}
} AC;

int main(){
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= n; i++) scanf("%s", P[i]), Plen[i] = strlen(P[i]), AC.insert(P[i], Plen[i], i);
	AC.build_fail();
	for(register int i = 1; i <= m; i++){
		scanf("%s", T), Tlen = strlen(T);
		printf("%d\n", AC.match_dp(T, Tlen));
	}
	return 0;
}