Как определить максимальную длину цепочки `XYZXYZXYZ`?

Question

Текстовый файл состоит не более чем из 10^6 символов X, Y и Z. Определите максимальную длину цепочки XYZXYZXYZ... (составленной из фрагментов XYZ, последний фрагмент может быть не полным). (вместо текстового файла строка)

Можно ли как-то сократить код, решить иначе?

var s := 'XYZXYZXYZYXYZUXYZ';
var t, maxt, i: integer;
while i < s.Length - 2 do
begin
  i += 1;
  if (s[i] = 'X') and (s[i + 1] = 'Y') and (s[i + 2] = 'Z') then
  begin
    t += 1;
    if t > maxt then
      maxt := t;
    i += 2;
  end
  else
    t := 0;
end;
maxt.Print;

Answer 1

Т.к. не указаны ограничения на используемые технологии, память и быстродействие, то в новых Delphi можно, например, регулярные выражения применить.

uses
  System.RegularExpressions;
  
const
  pattern = '(XYZ)+(XY|X)?';
  content = 'XYZXYZXXYYXYZXYZXYZZXYXYZXYZXYZXYZYYZXYXYZXXYZZXYZXYZXY';

var
  e: TMatch;
  l: Integer;

begin
  l := 0;
  for e in TRegEx.Matches( content, pattern ) do
    if ( e.Length > l ) then
      l := e.Length;

  Writeln( l );
end;

Answer 2

Как правило хотят не сократить код, а ускорить вычисления. Для такой задачи отлично может подойти конечный автомат. Теория вычислений. Введение в конечные автоматы. В данном случае это сделать просто (даже таблицу переходов отдельно делать не нужно). И скорость будет максимальной (на каждом шаге у нас будет одно сравнение вместо трех). Хорошо реализованный RegEx тоже должен давать хорошую скорость.

PS. Если нужен код, то пиши.

БЛОГ НА HUSL

Как определить максимальную длину цепочки `XYZXYZXYZ`?

Ответы (2 шт):