现在的位置: 首页 > 综合 > 正文

poj2192

2018年01月15日 ⁄ 综合 ⁄ 共 666字 ⁄ 字号 评论关闭

【题意】

给定字符串A字符串B字符串C,问A和B是否能按顺序交错成为C

【输入】

第一行n,表示数据组数

每组数据一行,三个字符串,中间用空格分隔

【输出】

对于数据i,输出"Data set "i": ","yes"或"no“

数据弱了一些,dp即可通过

f[i][j]表示A的前i个和B的前j个是否能拼成C的前i+j个

program poj2192;
var
  a,b,c:ansistring;
  n,i,j,k:longint;
  f:array [0..201,0..201] of boolean;

begin
  readln(n);
  for k:=1 to n do
    begin
      readln(c);
      a:=copy(c,1,pos(' ',c)-1);
      delete(c,1,pos(' ',c));
      b:=copy(c,1,pos(' ',c)-1);
      delete(c,1,pos(' ',c));
      fillchar(f,sizeof(f),false);
      f[0,0]:=true;
      for i:=0 to length(a) do
        for j:=0 to length(b) do
          if i+j<>0 then
            begin
              if (i>0)and(a[i]=c[i+j]) then
                f[i,j]:=f[i,j] or f[i-1,j];
              if (j>0)and(b[j]=c[i+j]) then
                f[i,j]:=f[i,j] or f[i,j-1];
            end;
      write('Data set ',k,': ');
      if f[length(a),length(b)] then writeln('yes')
                                else writeln('no');
    end;
end.
【上篇】
【下篇】

抱歉!评论已关闭.