最长前缀

Description
一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为基元（字符串）的序列。对于给定的基元集合P，如果可以从中选出N个基元P1，P2，P3，...,Pn，将它们各自对应的字符串依次连接后得到一个字符串S，称S可以由基元集合P构成。在从P中挑选基元时，一个基元可以使用多次，也可不用。例如，序列 ABABACABAAB 可以由基元集合{A，AB，BA，CA，BBC} 构成。
字符串的前K个字符为该字符串的前缀，其长度为K。请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，要求该前缀的长度尽可能长，输出其长度。
Input
　　输入数据的开头是基元集合P,包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格或者回车键分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的一行。集合中的元素没有重复。接着是大写字母序列T ，长度为 1..200,000 ，用一行或者多行的字符串来表示。换行符并不是序列T的一部分。
Output
只有一行，输出一个整数，表示基元集合P构成的字符串T的前缀的长度。
Sample Input
A AB BA CA BBC
ABABACABAABC

 

 

my $instr = "ababacabaabc";
my @prefixes = ("a", "ab", "ba","ca","bbc");
my @result;
for my $index (1 .. length($instr)){
    my $curstr = substr($instr, length($instr) - $index);
    my $pref;
    for(@prefixes){
        if(substr($curstr, 0, length($_)) eq $_){
            my $tpref = $_.$result[length($instr) - $index + length($_)];
            $pref = $tpref if( !defined($pref) or length($tpref) > length($pref));
        }
    }
    $result[length($instr) - $index] = $pref;
}
print $result[0];