【题解】 [HNOI2004] L 语言
题目传送门
题意
题目描述
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。
一段文章 \(T\) 由若干小写字母构成。一个单词 \(W\) 也是由若干小写字母构成。一个字典 \(D\) 是若干个单词的集合。我们称一段文章 \(T\) 在某个字典 \(D\) 下是可以被理解的，是指如果文章 \(T\) 可以被不重不漏地分成若干部分，且每一个部分都是字典 \(D\) 中的单词。
给定一个字典\(D\)，你的程序需要判断若干段文章在字典 \(D\) 下是否能够被理解，并给出其在字典 \(D\) 下能够被理解的最长前缀的位置。
输入格式
第一行两个整数 n 和 m，表示字典 D 中有 n 个单词，且有 m 段文章需要被处理。
接下来 n 行，每行一个字符串 s，表示字典 D 中的一个单词。
接下来 m 行，每行一个字符串 t，表示一篇文章。
输出格式
对于输入的每一篇文章，你需要输出一行一个整数，表示这段文章在字典 \(D\) 可以被理解的最长前缀的位置。
思路
由于你谷的数据有加强，所以主要以你谷上的得分为对照。
壹
文本串的前缀\(s[0,i]\)能被理解，当且仅当某个位置\(j \in [0,j)\)满足\(s[0,j]\)能够被理解，并且\(s[j+1,i]\)能够被理解。
一个朴素的想法：
用und数组记录文本串\(s[0,und[tmp]]\)恰好能被理解时的位置。文本串从头到尾遍历，每次都枚举und里表示的能被理解的前缀，然后在字典里面验证\(s[und[j]+1,i]\)是否能被理解。最后更新und数组。
用f数组记录截至当前的i，能够被理解的最长前缀。由于能被理解的最长前缀长度序列不下降，因此递推时只需要取当前和前一位置f数组的较大值。
朴素的算法必无法从这题手里骗到满分。事实上，\(O(大约n^2)\)的时间复杂度实在算不得优秀。
55pts on Luogu-Code1
#include
using namespace std;
#define ll long long
const int N=2e6+5;
int n,m,lm;
string w;
int trie[500][27],cnt;
bool ex[500];
ll f[N],und[N],tmp;
inline ll lkup(ll l,ll r){
if(l>r) return 0;
int p=0;
ll ret=0;
for(int i=l;i<=r;i++){
int c=w[i]-'a';
if(!trie[p][c]) return ret;
p=trie[p][c];
if(ex[p]) ret=i-l+1;
}
if(ex[p]) ret=r-l+1;
return ret;
}
inline ll find(string s){
memset(f,0,sizeof(f));
tmp=0;
int l=s.length();
for(int i=0;i=0;j--){
f[i]=max(f[i],und[j]+1+lkup(und[j]+1,(ll)i));//[j+1,i]
if(f[i]==i+1) break;
}
f[i]=max(f[i],f[i-1]);
if(f[i]==i+1) und[tmp++]=i;
}
return f[l-1];
}
inline void ins(string str){
int l=str.length();
lm=max(lm,l);
int p=0;
for(int i=0;i'z') ch=getchar();
while(ch>='a' && ch<='z'){
s+=ch;
ch=getchar();
}
return s;
}
int main(){
scanf("%d%d",&n,&m);
while(n--){
w=read();
ins(w);
}
while(m--){
w=read();
printf("%lld\n",find(w));
}
return 0;
}
贰
Many days later……
据说正解是AC自动机，那就先打一个AC自动机板子吧（错误思想）。
怎么保证连着匹配前缀呢？打到最后灵光一闪，直接在trie上比较就可以了啊！哪里用得着什么AC自动机！
这次打出来和Code1有几点不同：
90 pts on Luogu-Code2
#include
using namespace std;
#define ll long long
const int S=2e6+5;
const int N=400;
int n,m,ml;
int tr[N*100][30],cnt;//,fail[N*100]（留着做纪念）
char s[N],t[S];
bool ex[N*100],f[S];
inline int query(char r[],int len,int st){
int p=0,ret=0;
len=min(st+ml,len);
for(int i=st;i 叁
90 pts on Luogu-Code
#include
using namespace std;
#define ll long long
const int S=2e6+5;
const int N=400;
int n,m,ml;
int tr[N*100][30],cnt;
char s[N],t[S];
bool ex[N*100],f[S];
ll zt;
inline int query(char r[],int len,int st) {
int p=0,ret=0;
len=min(st+ml,len);
for(int i=st; i>=1,i++;
while(i>=1; i++;
while(!(zt&1) && zt) zt>>=1,i++;
}
return ret;
}
inline void ins(char r[]) {
int l=strlen(r);
ml=max(ml,l);
int p=0;
for(int i=0; i “人类的使命，在于自强不息地追求完美”，文学巨匠托尔斯泰曾言。虽然至此，已经可以ACLOJ上的题目，但是没有过你谷上的加强样例，笔者怎么会止歇？
肆
One day later……
笔者再次遇到了瓶颈。
“不破不立”，只有敢于挑战思维定式，才能创造新的成果，突破瓶颈。我在瞎写
代码实现
AC Code
#include
using namespace std;
#define ll long long
const int S=2e6+5;
const int N=405;
int n,m;
int tr[N*100][30],cnt,ex[N*100],fail[N*100];
int f[S],len[N*100],trans[N*100];
char s[N],t[S];
inline int query(char r[]) {
int p=0,x=0;
int l=strlen(r+1);
f[0]=1;
for(int i=1; i<=l; i++) {
p=tr[p][r[i]-'a'];
x=((x<<1)|f[i-1])&((1<<20)-1);
f[i]=(x&len[p])!=0;
}
for(int i=l;i>=1;i--){
if(f[i]) return i;
}
return 0;
}
inline void build_AC(){
queue q;
for(int i=0;i<26;i++){
if(tr[0][i]) q.push(tr[0][i]);
}
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tr[p][i]){
q.push(tr[p][i]);
fail[tr[p][i]]=tr[fail[p]][i];
}
else tr[p][i]=tr[fail[p]][i];
}
}
for(int i=1;i<=cnt;i++){
int j=i;
while(j){
if(ex[j]) len[i]|=(1<<(ex[j]-1));
j=fail[j];
}
}
}
inline void ins(char r[]) {
int l=strlen(r);
int p=0;
for(int i=0; i