问题描述
是的,经典的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
这篇关于编码挑战:两个字符串中包含的最长子字符串的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!