记录编号	51779	评测结果	AAAAAA
题目名称	[IOI 1996][USACO 2.3] 最长前缀	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2012-12-31 19:43:43	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
string s;//用来算前缀的序列
int ls;//序列长度
class stset{
	public:
	string s;
	int l;
};
stset st[201];
int f[200001]={0};
int ssize=0;//集合中有多少个元素,USACO不给元素个数这是作死......
void input(void){
	string temp=" ";
	char ch[200]={0};
	while(scanf("%s",&ch)==1){
		if(ch[0]=='.') break;
		temp=ch;
		st[ssize].s=temp,st[ssize].l=temp.size();
		ssize++;
	}//这明媚而忧伤的输入......
	while(scanf("%s",&ch)==1){
		temp=ch;
		s+=temp;
	}
	ls=s.size();
}
bool belong(int left,int right){//前缀中[left,right]是否在集合中
	int len=right-left+1;
	bool flag=false;
	int i,j;
	for(i=0;i<ssize;i++){
		if(st[i].l!=len) continue;
		flag=true;
		for(j=0;j<st[i].l;j++){
			if(st[i].s[j]!=s[left+j]){
				flag=false;
				break;
			}
		}
		if(flag) return true;
	}
	return false;
}
void dp(void){
	int i,j;
	for(i=ls-1;i>=0;i--){
		for(j=0;j<10&&i+j<ls;j++){
			if(belong(i,i+j)&&f[i]<f[i+j+1]+j+1) f[i]=f[i+j+1]+j+1;
		}
	}
}
int main(){
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	input();
	dp();
	printf("%d\n",f[0]);
	return 0;
}