生物基元问题【动态规划 DP专题训练】 1260

一个生物体的结构可以用“基元”的序列表示,一个“基元"用一些英文字符串表示。对于一个基元集合P,可以将字符串S看作由n个基元P1,P2,…,Pn依次连接而成的。问题是给定一个字符串S和一个基元集合P,使S的前缀可由P中的基元组成。求这个前缀的最大长度。基元的个数最大为20，长度最大为20,字符中的长度最大为500000.例如基元集合为{A,AB,BBC,CA },字符串为ABACABBCAACCB,则最大长度为10,其具体组成为ABACABBCAA 2214433311

第一行为字符串S，第二行为一个整数m，表示基元数 以下m行，每行一个基元

只有一个整数，表示字符串S中能得到的最大前缀长度。