string - 字符串集中最长的前缀+后缀组合

Question

我有一组长度为 1 到 ~30 的字符串(少于 30 个)。我需要找到至少两个字符串的子集，这些字符串共享最长的前缀+后缀组合。

例如设集合为

Foobar
Facar
Faobaron
Gweron
Fzobar

前缀/后缀 F/ar 的组合长度为 3，由 Foobar、Facar 和 Fzobar< 共享;前缀/后缀 F/obar 的组合长度为 5，由 Foobar 和 Fzobar 共享。搜索的前缀/后缀是F/obar。

请注意，不要将这与最长公共(public)前缀/后缀混淆，因为该集合中只有两个或多个字符串需要共享相同的前缀+后缀。另请注意，前缀和后缀的长度之和是要最大化的长度，因此两者都需要考虑在内。前缀或后缀可以是空字符串。

有人知道实现它的有效方法吗？

Answer 1

这个怎么样:

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) 部分中，它消除了比新发现的短的任何现有前缀/后缀(绞车重复)。