type
  arr=array [1..100000] of char;
var
  next:array [1..100000] of longint;
  s1,s2:arr;
  l2,l1:longint;
  ch:char;
procedure KMP_SELF(s1:arr);
var
  i,j:longint;
begin
  fillchar(next,sizeof(next),0);
  j:=0;
  for i:=1 to l1 do 
    begin
      if (j<>0) and (s1[j+1]<>s1[i]) then j:=next[j];
      if s1[j+1]=s1[i] then inc(j);
      next[i]:=j;
    end;
end;
procedure KMP(s1,s2:arr);
var
  i,j:longint;
begin
  j:=0;
  for i:=1 to l2 do 
    begin
      if (j<>0) and (s1[j+1]<>s2[i]) then j:=next[j];
      if s1[j+1]=s2[i] then inc(j);
      if j=l1 then
        begin
          writeln('Yes');
          j:=next[j];
          exit;
        end;
    end;
  writeln('No');
end;
begin
  while not eof do
    begin
      read(ch);
      while ch<>' ' do begin inc(l1);s1[l1]:=ch;read(ch); end;
      read(ch);
      while ord(ch)<>13 do begin inc(l2);s2[l2]:=ch;read(ch); end;
      read(ch);
      KMP_SELF(s1);
      KMP(s1,s2);
    end;
end.





我手残

• Re:KMP居然T了 (1153) zhangyufei 2015-12-13 23:10:56