MNE07 - OR Xâu

Tác giả: RR

Ngôn ngữ: Pascal

{$H-}
const
  FINP='';
  FOUT='';
  MAXN=5011;

label 1;

var
  f1,f2:text;
  a,b,c:string;
  next:array[1..MAXN] of longint;
  n,k,i,j:longint;

begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
  readln(f1,a); readln(f1,b);
  n:=length(a);
  a:=a+a;    b:=b+b;

  for i:=1 to n do
    begin
      c:=''; k:=i;
      for j:=1 to n do
        begin
          if (b[j]='0') and (b[k]='0') then c:=c+'0'
          else c:=c+'1';
          inc(k); if k>n then k:=1;
        end;

      next[1]:=0; k:=0;
      for j:=2 to n do
        begin
          while (k>0) and (c[j]<>c[k+1]) do k:=next[k];
          if c[j]=c[k+1] then inc(k);
          next[j]:=k;
        end;

      k:=0;
      for j:=1 to n shl 1 do
        begin
          while (k>0) and (a[j]<>c[k+1]) do k:=next[k];
          if a[j]=c[k+1] then inc(k);
          if k=n then
            begin
              writeln(f2,'Yes');
              goto 1;
            end;
        end;
    end;

  writeln(f2,'No');
1:
  close(f1); close(f2);
end.

Download