Question

How to find the shortest identical consecutive subarray in an array with Pascal

Answer 1

program ShortestRunProgram;

type
  IntArray = array of Integer;

function shortest_identical_consecutive_subarray(arr: IntArray): IntArray;
var
  bestStart, bestLen: Integer;
  currentStart, currentLen: Integer;
  i: Integer;
  resultArr: IntArray;
begin
  if Length(arr) = 0 then
  begin
    SetLength(resultArr, 0);
    shortest_identical_consecutive_subarray := resultArr;
    Exit;
  end;

  bestStart := 0;
  bestLen := Length(arr);

  currentStart := 0;
  currentLen := 1;

  for i := 1 to Length(arr) - 1 do
  begin
    if arr[i] = arr[i - 1] then
      Inc(currentLen)
    else
    begin
      if currentLen < bestLen then
      begin
        bestLen := currentLen;
        bestStart := currentStart;
      end;
      currentStart := i;
      currentLen := 1;
    end;
  end;

  if currentLen < bestLen then
  begin
    bestLen := currentLen;
    bestStart := currentStart;
  end;

  SetLength(resultArr, bestLen);
  for i := 0 to bestLen - 1 do
    resultArr[i] := arr[bestStart + i];

  shortest_identical_consecutive_subarray := resultArr;
end;

var
  arr: IntArray;
  resultArr: IntArray;
  i: Integer;

begin
  SetLength(arr, 19);
  arr[0] := 3; arr[1] := 3; arr[2] := 3;
  arr[3] := 7; arr[4] := 7; arr[5] := 7; arr[6] := 7; arr[7] := 7;
  arr[8] := 2; arr[9] := 2;
  arr[10] := 5; arr[11] := 5; arr[12] := 5; arr[13] := 5;
  arr[14] := 9; arr[15] := 9; arr[16] := 9; arr[17] := 9; arr[18] := 9;

  resultArr := shortest_identical_consecutive_subarray(arr);

  Write('Array result: ');
  for i := 0 to Length(resultArr) - 1 do
    Write(resultArr[i], ' ');
end.




(*
run:

Array result: 2 2 

*)

 

70+ SQL courses for beginners and professionals