本文介绍了编码挑战:两个字符串中包含的最长子字符串的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

是的,经典的LCS问题。给定两个或多个字符串找到每个字符串中最长的公共子字符串。



一个警告:没有C#,C,C ++,Javascript或任何 [],也不是任何基于VB的语言(VB,VB.NET,VBScript)。这削减了大多数简单的语言。展开你的翅膀!



你的解决方案应该考虑空字符串和字符串,其长度仅受可用存储空间的限制。



我尝试了什么:



用于时差的褪黑激素但它不起作用。



Graeme_Grant再次获得了他的出色表现的根西岛,而且我认为,上周问题需要耗费时间。 Noice。

Yes, the classic LCS problem. Given two or more strings find the longest common substring in each string.

One caveat: No C#, C, C++, Javascript or any C-based programming language[^], nor any VB-based language (VB, VB.NET, VBScript). That cuts out most of the easy languages. Spread your wings!

Your solution should take into account null strings and strings whose length is limited only by available storage.

What I have tried:

Melatonin for jetlag but it doesn't work.

Graeme_Grant again gets the guernsey for his outstanding and, I'm assuming, time consuming treatment of last week's problem. Noice.

推荐答案

Program LongestSubstringContained(output);
type
    dynStrings = array of string;

procedure QuickSort(input : dynStrings; lowPos, highPos : integer);
var
  movablePointer, immovablePointer, temporaryPointer : integer;
  temporaryItem : string;

begin
  immovablePointer := lowPos; 
  movablePointer := highPos;

  while (movablePointer <> immovablePointer) do
  begin
    if(movablePointer > immovablePointer) then
    begin
      if(input[movablePointer] < input[immovablePointer]) then
      begin
        temporaryItem := input[movablePointer];
        input[movablePointer] := input[immovablePointer];
        input[immovablePointer] := temporaryItem;

        temporaryPointer := movablePointer; 
        movablePointer := immovablePointer;
        immovablePointer := temporaryPointer;
      end
      else
      begin
        dec(movablePointer); 
      end;
    end
    else
    begin
      if(input[movablePointer] > input[immovablePointer]) then
      begin
        temporaryItem := input[movablePointer];
        input[movablePointer] := input[immovablePointer];
        input[immovablePointer] := temporaryItem;

        temporaryPointer := movablePointer;
        movablePointer := immovablePointer;
        immovablePointer := temporaryPointer;
      end
      else
      begin
        inc(movablePointer);
      end;
    end;
  end;

  if(movablePointer > lowPos) then
    QuickSort(input,lowPos,movablePointer-1);

  if(movablePointer < highPos) then
    QuickSort(input,movablePointer+1,highPos);
end;

//remove blank array entries...
function TrimArray(input: dynStrings) : dynStrings;
var
    i, len, count: integer;
    ret: dynStrings;

begin
    count := 0;
    len := Length(input);
    for i := 0 to len do
    begin
        if (Length(input[i]) > 0) then
        begin
            count := count + 1;
            setlength(ret, count);
            ret[count - 1] := input[i];
        end;
    end;
    TrimArray := ret;
end;

function RetrieveBestResult(strings :dynStrings) : string;
var
    str, tmp: string;
    strLen, strCount, i, len, tmpCount: integer;

begin
    tmpCount := 0;
    strCount := 0;
    strLen := 0;
    tmp := '';
    str := '';

    // order the array
    QuickSort(strings, low(strings), high(strings));
    // find the most popular longest string
    for i := 0 to high(strings) do
    begin
        len := length(strings[i]);
        if (len >= strLen) then
        begin
            strCount := 1;
            str := strings[i];
            strLen := len;
        end
        else if (str = strings[i]) then
            strCount := strCount + 1

        else if (tmp = strings[i]) then
            tmpCount := tmpCount + 1
        else
        begin
            tmp := strings[i];
            tmpCount := 1;
        end;
    end;
    RetrieveBestResult := str;
end;

// check for a match
function StrInArray(value : string; strings :dynStrings) : Boolean;
var
    str : String;

begin
    for str in strings do
    begin
        if length(value) = 0 then
            exit(false);
       //if (lowercase(value) = lowercase(str)) then
       if (value = str) then
        begin
            exit(true);
        end;
    end;
  StrInArray := false;
end;

function Process(input: dynStrings) : string;
var
    matches: dynStrings;
    allMatches: dynStrings;
    i, c, cc, count, len: integer;
    str, sstr: string;

begin
    setlength(allMatches, 0);
    setlength(matches, 0);
    for i := 0 to high(input) do
    begin
        str := input[i];
        count := 0;
        len := length(str);
        for c := 0 to len do
        begin
            for cc := 1 to len - c do
            begin
                sstr := copy(str, c, cc);
                if (high(allmatches) = -1) or (StrInArray(sstr, allMatches)) then
                begin
                    count := count + 1;
                    setlength(matches, count);
                    matches[count - 1] := sstr;
                end;
            end;
        end;
        // bounce early if no matches
        if (high(matches) < 1) then
            exit('no match');
        allMatches := copy(matches, 0, length(matches));
        writeln('Matches found: ', high(allMatches));
        setlength(matches, 0);
    end;
    Process := RetrieveBestResult(allMAtches);
end;

function GetLCS(input: dynStrings) : string;
var
    count: integer;
    work: dynStrings;

begin
    // check and clean
    count := Length(input);
    if (count = 0) then
        exit('empty')
    else
    begin
        work := TrimArray(input);
        count := Length(work);
        if (count = 0) then
            exit('empty');
    end;
    // process if work to be done...
    writeln('processing...');
    GetLCS := Process(work);
end;

var
    tests: array[0..4] of string;
    result: string;

begin
    tests[0] := 'Yes, the classic LCS problem. Given two or more strings find the longest common substring in each string.';
    tests[1] := '';
    tests[2] := 'One caveat: No C#, C, C++, Javascript or any C-based programming language[^], nor any VB-based language (VB, VB.NET, VBScript). That cuts out most of the easy languages. Spread your wings!';
    tests[3] := '';
    tests[4] := 'Your solution should take into account null strings and strings whose length is limited only by available storage.';

    result := GetLCS(tests);
    writeln('Longest Substring: ', result);
end.



这是输出...


And here is the output...

sh-4.3




这篇关于编码挑战:两个字符串中包含的最长子字符串的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-20 21:16