Question

How to find the longest common prefix of all the words in a string with Pascal

Answer 1

program LongestCommonPrefix;

const
  MaxWords = 64;
  MaxLen   = 128;

type
  TStringArray = array[1..MaxWords] of string;

function ToLowerStr(s: string): string;
var
  i: integer;
begin
  for i := 1 to Length(s) do
    if s[i] in ['A'..'Z'] then
      s[i] := Chr(Ord(s[i]) + 32);
  ToLowerStr := s;
end;

function ExtractWords(s: string; var words: TStringArray): integer;
var
  i, count: integer;
  current: string;
begin
  count := 0;
  current := '';
  s := ToLowerStr(s);

  for i := 1 to Length(s) do
  begin
    if s[i] in ['a'..'z'] then
      current := current + s[i]
    else if current <> '' then
    begin
      Inc(count);
      words[count] := current;
      current := '';
    end;
  end;

  if current <> '' then
  begin
    Inc(count);
    words[count] := current;
  end;

  ExtractWords := count;
end;

function LCP2(a, b: string): string;
var
  i: integer;
begin
  i := 1;
  while (i <= Length(a)) and (i <= Length(b)) and (a[i] = b[i]) do
    Inc(i);
  LCP2 := Copy(a, 1, i - 1);
end;

procedure SortWords(var words: TStringArray; n: integer);
var
  i, j: integer;
  temp: string;
begin
  for i := 1 to n - 1 do
    for j := i + 1 to n do
      if words[j] < words[i] then
      begin
        temp := words[i];
        words[i] := words[j];
        words[j] := temp;
      end;
end;

function LongestCommonPrefix(s: string): string;
var
  words: TStringArray;
  n: integer;
begin
  n := ExtractWords(s, words);
  if n = 0 then
  begin
    LongestCommonPrefix := '';
    Exit;
  end;

  SortWords(words, n);

  LongestCommonPrefix := LCP2(words[1], words[n]);
end;

var
  s1, s2: string;

begin
  s1 := 'The lowly inhabitants of the lowland were surprised to see the lower branches.';
  writeln('LCP: ''', LongestCommonPrefix(s1), ''''); 

  s2 := 'unclear, uncertain, unexpected';
  writeln('LCP: ''', LongestCommonPrefix(s2), ''''); 
end.




(*
run:

LCP: ''
LCP: 'un'

*)

 

70+ SQL courses for beginners and professionals