统计单词个数

统计单词个数

[问题描述]
　　给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字串分成k份（1<k≤40），且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，选用this之后就不能包含th）。
　　单词在给出的一个不超过6个单词的字典中。
　　要求输出最大的个数。
[输入格式]
　　全部输入数据存放在文本文件input3.dat中，其格式如下：
　　第一行为一个正整数(0<n≤5)表示有n组测试数据
　　每组的第一行有二个正整数：（p,k)
　　　　p表示字串的行数；
　　　　k表示分为k个部分。
　　接下来的p行，每行均有20个字符。
　　再接下来有一个正整数s，表示字典中单词个数。（1≤s≤6）
　　接下来的s行，每行均有一个单词。
[输出格式]
　　结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。
[样例]
输入：1
　　　1 3
　　　thisisabookyouareaoh
　　　4
　　　is
　　　a
　　　ok
　　　sab
输出：　　　　　//说明：（不必输出）
　　　7 　　　　// this/isabookyoua/reaoh
　　　　　　　　　　　　 sab

　

programtg20013;
const maxl=200;
type chararr=string[maxl];
var n,p,k,s,l,i,max: integer;
word:array[1..6] of chararr;
s1:chararr;
str:array[1..10] of string[20];
fi:text;
f:array[1..maxl] of integer;
len:array[1..maxl] of integer;
g:array[1..maxl,1..maxl] of byte;
function plus(str:chararr):integer;
var l1,r,i,j,x:integer;
   b:array[1..200] of boolean;
begin
x:=0;
l1:=length(str);
fillchar(b,sizeof(b),true);
for j:= 1 to s do
  begin
   r:=length(word[j]);
   for i:= 1 to l1 do
    if (word[j]=copy(str,i,r)) and b then beginb:=false;x:=x+1 end
  end;
plus:=x;
end;
procedure calclen;
var i,j:integer;
begin
for i:=1 to l do len:=200;
for i:=1 to l do
  for j:=1 to s do
   if copy(s1,i,length(word[j]))=word[j] then if
   len>length(word[j]) then len:=length(word[j]);
end;
procedure calc_g;
var i,j:integer;
begin
fillchar(g,sizeof(g),0);
for i:=l downto 1 do
begin
  if len=1 then g[i,i]:=1 ;
  for j:=l-1 downto 1 do
   if len[j]<=i-j+1 then g[j,i]:=g[j+1,i]+1 else g[j,i]:=g[j+1,i];
end;
end;
procedure calc;
var  i,j,m,maxt,t:integer;stri:string;
begin
for i:=1 to l do
  f:=plus(copy(s1,1,i));
for i:=2 to k do
   begin
    for j:=l downto 1 do
      begin
       maxt:=0;
       for m:=i-1 to j-1 do
         begin
         t:=f[m]+g[m+1,j];
         if t>maxt then maxt:=t;
         end;
        f[j]:=maxt;
      end;
end;
end;
begin
assign(fi,'input3.dat');
reset(fi);
readln(fi,n);
repeat
  dec(n);
  readln(fi,p,k);
  s1:='';
  for i:=1 to p do
   begin
    readln(fi,str);
    s1:=s1+str;
   end;
  l:=length(s1);
  readln(fi,s);
  for i:=1 to s do
   readln(fi,word);
  calclen;
  calc_g;
  calc;
  writeln(f[l]);
  until n=0;
end.