左儿子右兄弟的trie，比较慢，甚至不如暴力匹配2333333
对了，开o2会WA一个点，不开能A，您凑合着看
```cpp
/*
ID: z8493331
LANG: C++
TASK: prefix
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using std::cin;
using std::max;
char all[400000];
char sub_seq[300][300],seq[200005];
int len[300];//len[0] is the length of the main sequence
int sub_cnt=0;
int sub_len=0;
struct node{
public:
char c;
bool end;
node* ch[2];
node(char c_):c(c_){ch[0]=ch[1]=NULL,end=false;};//×ó¶ù×ÓÓÒÐÖµÜ
};
node* trie;
void insert(node* &o,const char a[],int pos){
/* if(a[pos]==o->c){
if(a[pos+1]=='\000'){
o->end=true;
return ;
}else{
if(o->ch[0]!=NULL)
insert(o->ch[0],a,pos+1);
else{
o->ch[0]=new node(a[pos+1]);
insert(o->ch[0],a,pos+1);
}
}
}else{*/
node* k=o;
while((k!=NULL)&&(k->c!=a[pos])){
k=k->ch[1];
}
if(k==NULL){
node* d=new node(a[pos]);;
if(a[pos+1]=='\000')
d->end=true;
d->ch[1]=o->ch[1];
o->ch[1]=d;
if(!d->end)
insert(o->ch[1],a,pos);
}else{
if(a[pos+1]!='\000'){
if(k->ch[0]==NULL)
k->ch[0]=new node(a[pos+1]);
insert(k->ch[0],a,pos+1);
}else{
k->end=true;
}
}
}
bool find(char a[],int pos,int t,node* o){
node* k=o;
while(k!=NULL&&k->c!=a[pos]) k=k->ch[1];
if(k==NULL) return false;
else{
if(pos==t){
if(k->end)
return true;
else
return false;
}
return find(a,pos+1,t,k->ch[0]);
}
}
void init(){
int tot=0;
while(all[tot]!=EOF){
all[++tot]=getchar();
}
int x=1;
while(1){
sub_cnt++;
sub_len=0;
while(all[x]<='Z'&&all[x]>='A'){
sub_seq[sub_cnt][++sub_len]=all[x];
x++;
}
len[sub_cnt]=sub_len;
while(all[x]>'Z'||all[x]<'A'){
if(all[x]=='.')
break;
x++;
}
if(all[x]=='.')
break;
}
while(all[x]<'A'||all[x]>'Z') x++;
sub_len=0;
while(all[x]!=EOF){
if(all[x]>='A'&&all[x]<='Z')
seq[++sub_len]=all[x];
x++;
}
len[0]=sub_len;
trie=new node('-');
for(int i=1;i<=sub_cnt;i++){
insert(trie,sub_seq[i],1);
}
}
bool f[200005];
bool check_match(int s,int t){
return find(seq,s,t,trie);
}
int dp(){
memset(f,0,sizeof(f));
f[0]=true;
int max_len=0;
for(int i=1;i<=sub_cnt;i++)
max_len=max(max_len,len[i]);
for(int i=1;i<=len[0];i++){
/*bool flag=true;
if(i>=max_len){
bool flag=true;
for(int j=1;j<=max_len;j++){
if(f[i-j])
flag=false;
}
if(flag){
return i-max_len-1;
}
}
for(int j=1;j<=sub_cnt;j++){
if(i>=len[j]&&check_match(i-len[j]+1,i)){
if(f[i-len[j]]){
f[i]=true;
break;
}
}
}*/
for(int j=max_len;j>=1;j--){
if(i<j)
continue;
if(f[i-j]){
if(check_match(i-j+1,i)){
f[i]=true;
break;
}
}
}
}
for(int i=len[0];i>=1;i--){
if(f[i])
return i;
}
}
int main(){
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
init();
printf("%d\n",dp());
return 0;
}
```
by Sarah @ 2018-03-06 19:34:48
Trie就是个废物
by sleepyNick @ 2018-08-28 21:58:19
是吗？@[mega_aspirin](/space/show?uid=22658)
by Epiphyllumthief @ 2018-09-14 10:48:00
做法同L语言。
不过读入要麻烦一点。
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
char s[1000001],ss[1000001];
int dp[1000001],ans,tot;
struct node{
int ch[27],end;
}t[1000001];
void build(){
int now=0,len=strlen(s+1);
for(int i=1;i<=len;i++){
if(!t[now].ch[s[i]-'A'])
t[now].ch[s[i]-'A']=++tot;
now=t[now].ch[s[i]-'A'];
}
t[now].end=1;
}
int main(){
freopen("data.in","r",stdin);
int ll=1;
while(1){
scanf("%s",s+1);
ll++;
if(s[1]=='.')break;
build();
}
int len=0;
while(scanf("%s",ss)==1){
int l=strlen(ss);
for(int i=0;i<l;i++)
s[++len]=ss[i];
}
dp[0]=1;
for(int i=0;i<=len;i++){
if(dp[i]){
ans=i;
int now=0;
for(int j=i+1;j<=len;j++){
now=t[now].ch[s[j]-'A'];
if(!now)break;
if(t[now].end)dp[j]=1;
}
}
}
printf("%d\n",ans);
return 0;
}
```
by Epiphyllumthief @ 2018-09-14 10:49:42