记录编号	451418	评测结果	AAAAAA
题目名称	[IOI 1996][USACO 2.3] 最长前缀	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2017-09-17 17:03:25	内存使用	1.08 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
using namespace std;
const int maxn=210;
const int maxl=200010;
string s;
string a[maxn];
int tot;
string c;
int d[maxl];//匹配到i的最长前缀； 
int main(){
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	ios::sync_with_stdio(false); 
	while(true){
		cin>>a[++tot];
		if(a[tot]=="."){
			tot--;break;
		}
	}
	while(cin>>c){
		s+=c;
	}
	for(int i=0;i<s.length();i++){
		for(int j=1;j<=tot;j++){
			if(i+1<a[j].length())continue;
			int ok=1;
			int len=a[j].length();
			for(int k=0;k<len;k++){//进行匹配；
				//if(a[j]=="AB")cout<<i+1<<" "<<j<<" "<<a[j][k]<<" "<<s[i-len+k+1]<<endl;
				if(a[j][k]!=s[i-len+k+1]){
					ok=0;
					break;
				}
			}
			if(ok==0){//匹配失败
				if(i-len>=0)
					d[i]=max(d[i-len],d[i]);
			}
			else{
				if(i-len>=0){
					if(d[i-len]==i-len+1)
						d[i]=d[i-len]+len;
				}
				if(i-len==-1){
					//cout<<a[j]<<endl;
					d[i]=i+1;
				}
			}
		}
	}
	int ansl=s.length()-1;
	cout<<d[ansl]<<endl;
	return 0;
}