# USACO 2.3 Longest Prefix

### 题目描述

The structure of some biological objects is represented by the sequence of their constituents, where each part is denoted by an uppercase letter. Biologists are interested in decomposing a long sequence into shorter sequences called primitives.

We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives

   {A, AB, BA, CA, BBC}

The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives

### Code

/*
PROB: prefix
LANG: C++
ID: yizhuor1
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
T sum = 0;
int fl = 1,ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int maxn = 2e5 + 5;

int size;
int dp[maxn];
string st;
set<string> s[20];

inline void Solve (){
int ans = 0;
dp[0] = 1;
string tmp;
tmp = " ";
while(cin >> st){
tmp = tmp + st;//把所有串合并成一个
}
for(int i = 1; i < tmp.size(); i++){//枚举子串
for(int j = min(i,size); j >= 1; j--){
string sub = tmp.substr(i - j + 1,j);
if(s[sub.size()].count(sub) == 1 && dp[i - j] == 1){
ans = i;
dp[i] = 1;//更新当前状态
break;
}
}
}
printf("%d\n",ans);
}

inline void Input (){
while(cin >> st){
if(st == ".") break;
s[st.size()].insert(st);//把所有长度相同的串丢到一个set里面
Chkmax(size,(int)(st.size()));
}
}

int main(){
//  freopen("prefix.in","r",stdin);
//  freopen("prefix.out","w",stdout);
Input();
Solve();
return 0;
}