Chris Maunder Ответов: 3

Задача кодирования: самая длинная подстрока, содержащаяся в двух строках

Да, классическая проблема LCS. При наличии двух или более строк найдите самую длинную общую подстроку в каждой строке.

Одно предостережение: никакого C#, C, C++, Javascript или любого другого Язык программирования на основе C[^], ни какой-либо язык на основе VB (VB, VB.NET, VBScript). Это отсекает большинство простых языков. Расправь крылья!

Ваше решение должно учитывать нулевые строки и строки, длина которых ограничена только доступным хранилищем.

Что я уже пробовал:

Мелатонин для джетлага, но он не работает.

Graeme_Grant снова получает Гернси за его выдающееся и, как я предполагаю, трудоемкое лечение проблемы прошлой недели. Шум.

Graeme_Grant

Спасибо, Крис. Но не совсем ... возиться во время просмотра фильма...

Итак, глядя на вашу ссылку, R отсутствует, но F# & amp; PowerShell в порядке ;)

Patrice T

Каким должен быть результат ? Только длина ? Подстрока ?

Graeme_Grant

"найти самую длинную общую подстроку" ... я предполагаю, что это общая подстрока...

Chris Maunder

Да.

Jon McKee

Perl считается основанным на C, а F# - нет? Это немного странно, ТБХ. Во всяком случае, Perl имеет меньше общего с C, чем F#. Кроме того, эта связь включает в себя B, который был предшественником C, который я нахожу озадачивающим.

Graeme_Grant

Я бы сдул пыль со своего С64, но Бейсик был запрещен...

Jon McKee

Он уточнил VB. Ничего не сказать о просто основной ;)

Graeme_Grant

Я посадил свой флаг с F# (второй раз я использовал его, кроме 3 недель назад - это была/есть крутая кривая обучения)... Однако впереди напряженная неделя, придется посмотреть, как все сложится и смогу ли я найти старый С64...

PIEBALDconsult

ВБ не пускают, реальный основной.
У меня есть VAX BASIC, HP BASIC и Turbo BASIC...

PIEBALDconsult

Ну, а как BCPL и B считаются C-подобными? Они пришли первыми! (И второе.)

PIEBALDconsult

Я думаю, что у меня есть Паскаль на одном из моих Альфасерверов. У меня есть лицензия. У меня также есть лицензия на COBOL...

Graeme_Grant

Это может помочь: Бесплатный Turbo Pascal для Windows 10[^]- не пробовали его мысли...

PIEBALDconsult

: кашель: победа 7: кашель:

Graeme_Grant

Удивительно, что вы можете найти с помощью Google, когда используете его... ;)
* Turbo Pascal для Windows 7[^] и
* Как запустить Turbo Pascal v7. 0 на Windows 7/8[^]

PIEBALDconsult

Если бы я захотел, то уже получил бы его. Раньше я использовал Turbo Pascal (и Turbo C), но теперь этого не делаю.

Graeme_Grant

ярмарка будит...

Graeme_Grant

Я нашел FreePascal online IDE пару часов назад, так как я никогда раньше не делал Pascal, я дал ему попробовать, и вы можете увидеть, что я сделал ниже. О, как же я соскучился по своей любимой IDE & the power of the .Чистые фреймворки!

PIEBALDconsult

Да, в свое время я любил Паскаль, особенно турбо, но как только я освоился с Си, я перестал его использовать. Я даже не могу читать свои программы на Паскале из колледжа.

Graeme_Grant

[неправильное место, поэтому переехал]

PIEBALDconsult

С другой стороны...
Turbo Pascal (5.5+) имеет ООП, а HP Pascal, вероятно, нет-я изучил "структуры данных" на VAX/DEC/HP Pascal еще в 80-х.
У меня есть рабочая реализация на C#, чтобы доказать алгоритм, который я разработал.
Но мне придется самому реализовать HashSet и словарь, и я не думаю, что сейчас мне это под силу.

Graeme_Grant

StrDict типа Паскаля ': массив массив string;'... Затем, чтобы использовать: 'var DictName: StrDict;' ? Но опять же, я только новичок в этом языке...
Моя [реализация Pascal] была основана на хэш-наборе как концепции, так и на реализации F# (которая была прототипирована за несколько минут в C#), которая фактически использует хэш-набор. ;)

Graeme_Grant

Кроме того, в Pascal отсутствуют многие языковые инструменты, найденные в dotnet Framework, поэтому вам также нужно будет реализовать их ... такие вещи, как сортировка, ручное удаление нулевых записей из разделенных строк, хэш-наборы и т. д...

PIEBALDconsult

Ну, если бы я знал, как получить доступ к .net из Pascal...: круто:

Graeme_Grant

Да, современные разработчики испорчены...

Graeme_Grant

Быстрый намек... делая версию Pascal, я обнаружил, что хэш-набор не требуется.

PIEBALDconsult

Мой алгоритм использует его. Если бы я мог быть уверен в 64 или менее строках, я бы использовал побитовые операторы вместо Int64.

PIEBALDconsult

Как насчет самой неправильной подстроки?..

Graeme_Grant

Разве это не будет просто самая длинная входная строка?

PIEBALDconsult

Полагаю, вы правы.

3 Ответов

Рейтинг:
2

Graeme_Grant

Хорошо, поскольку F# приемлемо, вот версия F#, которая будет принимать несколько входных данных для сравнения и возвращать "самую длинную общую подстроку". Я использую текст задачи (включая нули) в качестве входных данных для тестирования... ;)

open System
open System.Collections.Generic
open System.Linq

let msg = "Yes, the classic LCS problem. Given two or more strings find the longest common substring in each string.\n\
           \n\
           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!\n\
           \n\
           Your solution should take into account null strings and strings whose length is limited only by available storage."

let tests = msg.Split [|'\n'|]

let GetSubstrings (s : string)  = 
    [ for c1 in 0 .. s.Length - 1 do
        for c2 in c1 .. s.Length - 1 do
                yield s.[c1..c2]
        ]

let addRange input (targetSet : ICollection<_>) =
        input |> Seq.iter(fun x -> targetSet.Add(x))

let GetLongestCommonSubstring (strings : string[]) =
    match (Seq.toList (strings.Where( fun x -> not(x.Equals(""))))) with
    | [] -> "empty"
    | x::xs -> 
        let subStrings = new HashSet<string>()
        addRange (GetSubstrings(x)) subStrings
        xs |> List.map(fun y -> 
            let yy = new HashSet<string>() 
            addRange (GetSubstrings(y)) yy 
            subStrings.IntersectWith(yy)) |> ignore
        subStrings.OrderByDescending(fun s -> s.Length).First()
        
[<EntryPoint>]
let main argv = 
    printfn "-----------------------------------------------------------------------\r\n"
    printfn "Input strings (including nulls / blank lines):\r\n"
    printfn "%A\r\n" msg
    printfn "-----------------------------------------------------------------------\r\n"
    printfn "** Longest common substring found is: %A\r\n" (GetLongestCommonSubstring(tests))
    printfn "\r\n-- Press any key to exit --";
    Console.ReadKey() |> ignore;
    0

... и выход:
-----------------------------------------------------------------------

Input strings (including nulls / blank lines):

"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."

-----------------------------------------------------------------------

** Longest common substring found is: "ings"


-- Press any key to exit --

Patrice T

Может быть, я устал, но в выводе, что такое первая строка и что такое вторая ?

Graeme_Grant

Мой вклад заключается в кавычках: "да, классика ... доступное хранилище. " - это 5 строк, 2-нули. Выход LCS после запуска кода над входом - это "ings"

Patrice T

Ладно, понятно.
Пара " вокруг каждой струны была бы для меня яснее.

Graeme_Grant

Нам не дали ничего для работы, так что да, это был блок текста, а не просто куча строк в массиве. Лучшим кандидатом оказался собственный текст вызова. Это позволяет использовать любое количество строк, а не только два (2). Первое, что я делаю, - это преобразую его в строковый массив.

Рейтинг:
2

PIEBALDconsult

Вот моя реализация C#, просто в качестве контрпримера.

Класс PIEBALD. Type.Substring похож на класс StringSlice, который я использовал для задачи фильтрации плохих слов, но с большим количеством наворотов.

public System.Collections.Generic.IList<string>
LCS
(
  params string[] Subject
)
{
  System.Collections.Generic.List<string> result = 
    new System.Collections.Generic.List<string>() ;

  System.Collections.Generic.Dictionary<PIEBALD.Type.Substring,System.Collections.Generic.HashSet<int>> temp =
    new System.Collections.Generic.Dictionary<PIEBALD.Type.Substring,System.Collections.Generic.HashSet<int>>() ;

  int shortest = System.Int32.MaxValue ;

  /* Find the shortest input length */
  for ( int i = 0 ; i < Subject.Length ; i++ )
  {
    if ( shortest > Subject [ i ].Length )
    {
      shortest = Subject [ i ].Length ;
    }
  }

  int max = 0 ;

  for ( ; ( max < Subject.Length ) && ( shortest > 0 ) ; shortest-- )
  {
    max = 0 ;

    temp.Clear() ;

    foreach 
    ( 
      PIEBALD.Type.Substring s 
    in 
      PIEBALD.Type.Substring.EnumSubstrings ( Subject [ 0 ] , shortest ) 
    )
    {
      temp [ s ] = new System.Collections.Generic.HashSet<int>() ;

      temp [ s ].Add ( 0 ) ;
    }

    for ( int i = 1 ; i < Subject.Length ; i++ )
    {
      foreach 
      ( 
        PIEBALD.Type.Substring s 
      in 
        PIEBALD.Type.Substring.EnumSubstrings ( Subject [ i ] , shortest ) 
      )
      {
        System.Collections.Generic.HashSet<int> v ;
                
        if ( temp.TryGetValue ( s , out v ) )
        {
          v.Add ( i ) ;

          if ( max < v.Count )
          {
            max = v.Count ;
          }
        }
      }

      if ( max < i )
      {
        break ;
      }
      else
      {
        // Remove dead entries maybe
      }
    }
  }

  foreach
  (
    System.Collections.Generic.KeyValuePair<PIEBALD.Type.Substring,System.Collections.Generic.HashSet<int>> kvp
  in 
    temp
  )
  {
    if ( kvp.Value.Count == Subject.Length )
    {
      result.Add ( kvp.Key.ToString() ) ;
    }
  }

  return ( result.AsReadOnly() ) ;
}

Рейтинг:
0

Graeme_Grant

Как будто F# был не так далек от нормального для меня (вторая попытка когда-либо), вот версия FreePascal для PIEBALDConsultant. Это моя первая попытка программирования на этом языке, поэтому, пожалуйста, будьте нежны, так как я уверен, что есть много возможностей для улучшения...

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.

А вот и выход...
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$ main                                                                                                                                                          
processing...                                                                                                                                                         
Matches found: 5564                                                                                                                                                   
Matches found: 253                                                                                                                                                    
Matches found: 147                                                                                                                                                    
Longest Substring: ings                                                                                                                                               
sh-4.3$

Это решение было построено с использованием Первом Кодирование [^] онлайн-IDE. Вот ссылка на решение[^] где вы можете скомпилировать и запустить его.

Наслаждайтесь! :)

Bryian Tan

Два решения от Graeme_Grant!!! Похоже, вы единственный участник !!!! :) в любом случае поздравляю вас с двумя предыдущими соревнованиями. Вы проделали огромную работу. Я думаю, что ты тоже получишь это.

Graeme_Grant

Спасибо, Брайан!

Второй был только после разговора с Пиебальдконсультантом... Никогда раньше не делал Паскаля, поэтому я решил попробовать.

Прыгай и вперед! [редактировать:] Я выучил 3 новых языка, выполняя эти задачи! :)

Bryian Tan

В любом случае, хорошая работа.