编码挑战：两个字符串中包含的最长子字符串 [英] Coding challenge: longest substring contained in two strings

问题描述

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



一个警告：没有C＃，C，C ++，Javascript或任何基于C的编程语言 [ ^ ]，也不是任何基于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.

推荐答案

好像F＃对我来说没有那么远（第二次尝试），这里是PIEBALDConsultant的FreePascal版本。这是我用这种语言编程的第一次尝试，所以请保持温和，因为我确信还有很大的改进空间...

As if F# was not as far away from normal for me (second attempt ever), here is a FreePascal version for PIEBALDConsultant. This is my first attempt at programming with this language, so please be gentle as I am sure there is plenty of room for improvement...

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

fpc -vw main.pas
免费Pascal编译器版本2.6.4 [2015/06/17] x86_64
Florian Klaempfl和其他人的版权所有（c）1993-2014
目标操作系统：Linux for x86-64
编译main.pas
链接主
/ usr / bin / ld：warning：link.res包含输出节;你忘记了吗？ 209行编译，0.1秒
sh-4.3

fpc -vw main.pas Free Pascal Compiler version 2.6.4 [2015/06/17] for x86_64 Copyright (c) 1993-2014 by Florian Klaempfl and others Target OS: Linux for x86-64 Compiling main.pas Linking main /usr/bin/ld: warning: link.res contains output sections; did you forget -T? 209 lines compiled, 0.1 sec sh-4.3

主
处理...
找到匹配项：5564
找到匹配项：253
找到匹配项：147
最长子串：ings
sh-4.3

main processing... Matches found: 5564 Matches found: 253 Matches found: 147 Longest Substring: ings sh-4.3

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