Самый длинный префикс + суффикс-комбинация в наборе строк - PullRequest
Новая
       12

Самый длинный префикс + суффикс-комбинация в наборе строк

0 голосов
/ 23 июня 2018

У меня есть набор строк (менее 30) длиной от 1 до ~ 30. Мне нужно найти подмножество как минимум из двух строк, которые разделяют максимально длинную комбинацию префикс + суффикс .

Например, пусть набор будет 

Foobar
Facar
Faobaron
Gweron
Fzobar

Префикс / суффикс F/ar имеет общую длину 3 и используется совместно Foobar, Facar и Fzobar; префикс / суффикс F/obar имеет общую длину 5 и используется совместно Foobar и Fzobar. Разыскиваемый префикс / суффикс: F/obar.

Обратите внимание, что это не следует путать с самым длинным общим префиксом / суффиксом, поскольку только две или более строк из набора должны иметь один и тот же префикс + суффикс. Также обратите внимание, что сумма длин как префикса, так и суффикса - это то, что должно быть максимизировано, поэтому оба должны быть приняты во внимание. Префикс или суффикс может быть пустой строкой.

Кто-нибудь знает эффективный метод для реализации этого?

1 Ответ

0 голосов
/ 24 июня 2018

Как насчет этого: 

maxLen := -1;
for I := 0 to Len(A) - 1 do
  if Len(A[I]) > maxLen then // (1)
    for J := 0 to Len(A[I]) do
      for K := 0 to Len(A[I]) - J do
        if J+K > maxLen then // (2)
        begin
          prf := LeftStr(A[I], J);
          suf := RightStr(A[I], K);
          found := False;
          for m := 0 to Len(sufList) - 1 do
            if (sufList[m] = suf) and (prfList[m] = prf) then
            begin
              maxLen := J+K;
              Result := prf+'/'+suf;
              found := True;
              // (3)
              n := 0;
              while n < Len(sufList) do
                if Len(sufList[n])+Len(prfList[n]) <= maxLen then
                begin
                  sufList.Delete(n);
                  prfList.Delete(n);
                end
                else
                  Inc(n);
              // (end of 3)
              Break;
            end;
          if not found then
          begin
            sufList.Add(suf);
            prfList.Add(prf);
          end;
        end;

В этом примере maxLen содержит сумму длин самого длинного найденного префикса / суффикса до сих пор. Наиболее важной частью является линия, помеченная (2). Он обходит множество ненужных сравнений строк. В разделе (3) он удаляет любой существующий префикс / суффикс, который короче вновь найденного (лебедка дублируется).

...