记录编号	88787	评测结果	AAAAAAAAAA
题目名称	1531.[IOI 1999]隐藏的码字	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	34.335 s
提交时间	2014-02-24 21:43:44	内存使用	206.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<fstream>
using namespace std;
const int SIZEN=101,SIZEC=53,SIZEL=1000001;
ifstream fin("hiddencode.in");
ofstream fout("hiddencode.out");
int N;
string code[SIZEN];
string text;
char letter[SIZEC]={0};//单词表
int last[SIZEL][SIZEC]={0};//第i位之前(严格)的第一个j的位置
class COVER{
public:
	int s,e;//起始位置
	int l;//匹配长度
};
bool operator < (COVER a,COVER b){
	if(a.e<b.e) return true;
	if(a.e>b.e) return false;
	if(a.s<b.s) return true;
	if(a.s>b.s) return false;
	return a.l<b.l;
}
vector<COVER> cov;
int f[SIZEL]={0};
int ans=0;
void DP(void){
	int p=0;
	for(int i=cov[0].e;i<=text.size();i++){
		f[i]=f[i-1];
		if(p==cov.size()) break;
		if(cov[p].e==i){
			while(cov[p].e==i&&p<cov.size()){
				f[i]=max(f[i],f[cov[p].s-1]+cov[p].l);
				p++;
			}
		}
		ans=max(ans,f[i]);
	}
}
int letterpos(char ch){
	if('a'<=ch&&ch<='z') return ch-'a'+1;
	if('A'<=ch&&ch<='Z') return ch-'A'+27;
	return 0;
}
int codematch(int x,int i,int j){//text[i-1]是code[x][j-1],返回这个涵盖串的首位置
	if(i==0) return 0;
	if(j==1) return i;
	return codematch(x,last[i][letterpos(code[x][j-2])],j-1);
}
void prepare(void){
	for(int i=1;i<=52;i++){//计算last
		int p=0;
		for(int j=1;j<=text.size();j++){
			last[j][i]=p;
			if(text[j-1]==letter[i]) p=j;
		}
	}
	int s;
	for(int i=1;i<=text.size();i++){
		for(int j=1;j<=N;j++){
			if(text[i-1]==code[j][code[j].size()-1]){
				s=codematch(j,i,code[j].size());
				if(s==0) continue;
				if(i-s+1>1000) continue;
				cov.push_back((COVER){s,i,code[j].size()});
			}
		}
	}
	sort(cov.begin(),cov.end());
}
void init(void){
	fin>>N;
	for(int i=1;i<=N;i++) fin>>code[i];
	fin>>text;
	for(int i=1;i<=26;i++) letter[i]='a'-1+i;
	for(int i=27;i<=52;i++) letter[i]='A'-27+i;
}
int main(){
	init();
	prepare();
	DP();
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}