TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1464
  • 题目
  • P1464最长前缀
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    一些生物体的复杂结构可以用其基元的序列表示,而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为基元(字符串)的序列。对于给定的基元集合P,如果可以从中选出N个基元P1,P2,P3,...,Pn,将它们各自对应的字符串依次连接后得到一个字符串S,称S可以由基元集合P构成。在从P中挑选基元时,一个基元可以使用多次,也可不用。例如,序列 ABABACABAAB 可以由基元集合{A,AB,BA,CA,BBC} 构成。

    字符串的前K个字符为该字符串的前缀,其长度为K。请写一个程序,对于输入的基元集合P和字符串T,求出一个可以由基元集合P构成的字符串T的前缀,要求该前缀的长度尽可能长,输出其长度。

    输入格式

    第一行是基元集合P中的基元数目N(1<=N<=100),随后有2N行,每两行描述一个基元,第一行为该基元的长度L(1<=L<=20)。随后一行是一个长度为L的大写英文字符串,表示该基元。每个基元互不相同。
    最后一行描述要处理的字符串T,T由大写字母组成,最后一行是一个字符'.',表示字符串结束。T的长度最小为1,最大不超过500000。

    输出格式

    只有一行,一个数字,表示可以由P构成的T的最长前缀的长度。

    样例输入

    5
    1
    A
    2
    AB
    3
    BBC
    2
    CA
    2
    BA
    ABABACABAABCB.

    样例输出

    11