# USACO Longest Prefix最长前缀 解题报告

Longest Prefix
IOI’96
The structure of some biological objects is represented by the sequence of their constituents denoted by uppercase letters. Biologists are interested in decomposing a long sequence into shorter ones 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.

PROGRAM NAME: prefix
INPUT FORMAT
First, the input file contains the list (length 1..200) of primitives (length 1..10) expressed as a series of space-separated strings of upper-case characters on one or more lines. The list of primitives is terminated by a line that contains nothing more than a period (‘.’). No primitive appears twice in the list. Then, the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceed 76 letters in length. The "newlines" are not part of the string S.
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC

OUTPUT FORMAT
A single line containing an integer that is the length of the longest prefix that can be composed from the set P.
SAMPLE OUTPUT (file prefix.out)
11

{A, AB, BA, CA, BBC}

PROGRAM NAME: prefix

INPUT FORMAT

OUTPUT FORMAT

SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
SAMPLE OUTPUT (file prefix.out)
11

============================ 华丽的分割线 ============================
前两天写出来了,, 忘记发日志了
感觉用的这个方法不像是DP(对于DP我还没有特别清楚的概念..),, 其中pre变量存储所有的匹配串(即短的那个字符串.), str是住串(长的那个.), 接下来最关键的是lenth这个变量,, (感觉名字没取好), 这个主串假设分为分为a1 a2 a3 … an, lenth[i]如果是1的话代表在a1 a2 a3 .. ai 都是能够在匹配串匹配..
说了一些云里雾里的话吧,, 废话不多,, 代码上:

/*
LANG: C
ID: zqy11001
PROG: prefix
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define getstr(s) scanf(%s, s)
char pre[401][11];
int m;

char lenth[200001];
char str[200000];
int n;

int main(void)
{
int i, j, k;
int best = 0;
freopen(prefix.in, r, stdin);
freopen(prefix.out, w, stdout);
while(1){
getstr(pre[m]);
if(pre[m][0] == \'.\'){
break;
}
m++;
}
while(getstr(str + n) == 1){
n += strlen(str + n);
}
lenth[0] = 1;
best = 0;
for(i = 0; i < n; i++){
if(lenth[i]){
best = i;
for(j = 0; j < m; j++){
for(k = 0; ((i + k) < n) && (pre[j][k] != \'\\0\') &&
(pre[j][k] == str[i + k]); k++){
;
}
if(pre[j][k] == \'\\0\'){
lenth[i + k] = 1;
}
}
}
}
if (lenth[n])
best = n;
printf(%d\\n, best);
return 0;
}`