Эффективный алгоритм для конкатенации строк с перекрытием

Вы можете использовать DFA. Например, строку XYZ следует читать с помощью регулярного выражения ^ ((A)? B)? C . Это регулярное выражение будет соответствовать самому длинному префиксу, который соответствует суффиксу строки XYZ . С таким регулярным выражением вы можете либо сопоставить и получить результат сопоставления, либо сгенерировать DFA, в котором вы можете использовать состояние, чтобы указать правильную позицию для «вырезки».

В Scala первая реализация - с использованием регулярное выражение напрямую - может выглядеть так:

def toRegex(s1: String) = "^" + s1.map(_.toString).reduceLeft((a, b) => "("+a+")?"+b) r
def concatWithoutMatch(s1 : String, s2: String) = {
  val regex = toRegex(s1)
  val prefix = regex findFirstIn s2 getOrElse ""
  s1 + s2.drop(prefix length)
}

Например:

scala> concatWithoutMatch("abXabXabXac", "XabXacd")
res9: java.lang.String = abXabXabXacd

scala> concatWithoutMatch("abc", "def")
res10: java.lang.String = abcdef

scala> concatWithoutMatch(concatWithoutMatch("abcde", "defgh"), "ghlmn")
res11: java.lang.String = abcdefghlmn

How about (pardon the C#):

public static string OverlapConcat(string s1, string s2)
{
    // Handle nulls... never return a null
    if (string.IsNullOrEmpty(s1))
    {
        if (string.IsNullOrEmpty(s2))
            return string.Empty;
        else
            return s2;
    }
    if (string.IsNullOrEmpty(s2))
        return s1;

    // Checks above guarantee both strings have at least one character
    int len1 = s1.Length - 1;
    char last1 = s1[len1];
    char first2 = s2[0];

    // Find the first potential match, bounded by the length of s1
    int indexOfLast2 = s2.LastIndexOf(last1, Math.Min(len1, s2.Length - 1));
    while (indexOfLast2 != -1)
    {
        if (s1[len1 - indexOfLast2] == first2)
        {
            // After the quick check, do a full check
            int ix = indexOfLast2;
            while ((ix != -1) && (s1[len1 - indexOfLast2 + ix] == s2[ix]))
                ix--;
            if (ix == -1)
                return s1 + s2.Substring(indexOfLast2 + 1);
        }

        // Search for the next possible match
        indexOfLast2 = s2.LastIndexOf(last1, indexOfLast2 - 1);
    }

    // No match found, so concatenate the full strings
    return s1 + s2;
}

This implementation does not make any string copies (partial or otherwise) until it has established what needs copying, which should help performance a lot.

Also, the match check first tests the extremeties of the potentially matched area (2 single characters) which in normal english text should give a good chance of avoiding checking any other characters for mismatches.

Only once it establishes the longest match it can make, or that no match is possible at all, will two strings be concatenated. I have used simple '+' here, because I think the optimisation of the rest of the algorithm has already removed most of the inefficiencies in your original. Give this a try and let me know if it is good enough for your purposes.

Или вы можете сделать это в mysql со следующей сохраненной функцией:

DELIMITER //

DROP FUNCTION IF EXISTS concat_with_overlap //

CREATE FUNCTION concat_with_overlap(a VARCHAR(100), b VARCHAR(100))
  RETURNS VARCHAR(200) DETERMINISTIC
BEGIN 
  DECLARE i INT;
  DECLARE al INT;
  DECLARE bl INT;
  SET al = LENGTH(a);
  SET bl = LENGTH(a);
  IF al=0 THEN 
    RETURN b;
  END IF;
  IF bl=0 THEN 
    RETURN a;
  END IF;
  IF al < bl THEN
     SET i = al;
  ELSE
     SET i = bl;
  END IF;

  search: WHILE i > 0 DO
     IF RIGHT(a,i) = LEFT(b,i) THEN
    RETURN CONCAT(a, SUBSTR(b,i+1));
     END IF;
     SET i = i - 1;
  END WHILE search;

  RETURN CONCAT(a,b);
END//

Я пробовал это с вашими тестовыми данными:

mysql> select a,b,c,
    -> concat_with_overlap( concat_with_overlap( a, b ), c ) as result 
    -> from testing //
+-------------+---------+--------+-------------+
| a           | b       | c      | result      |
+-------------+---------+--------+-------------+
| a           | b       | c      | abc         |
| abcde       | defgh   | ghlmn  | abcdefghlmn |
| abcdede     | dedefgh |        | abcdedefgh  |
| abcde       | d       | ghlmn  | abcdedghlmn |
| abcdef      |         | defghl | abcdefghl   |
| abXabXabXac | XabXac  |        | abXabXabXac |
+-------------+---------+--------+-------------+
6 rows in set (0.00 sec)

Вот решение на Python. Это должно быть быстрее, потому что вам не нужно постоянно создавать подстроки в памяти. Работа выполняется в функции _concat, которая объединяет две строки. Функция concat - это помощник, который объединяет любое количество строк.

def concat(*args):
    result = ''
    for arg in args:
        result = _concat(result, arg)
    return result

def _concat(a, b):
    la = len(a)
    lb = len(b)
    for i in range(la):
        j = i
        k = 0
        while j < la and k < lb and a[j] == b[k]:
            j += 1
            k += 1
        if j == la:
            n = k
            break
    else:
        n = 0
    return a + b[n:]

if __name__ == '__main__':
    assert concat('a', 'b', 'c') == 'abc'
    assert concat('abcde', 'defgh', 'ghlmn') == 'abcdefghlmn'
    assert concat('abcdede', 'dedefgh', '') == 'abcdedefgh'
    assert concat('abcde', 'd', 'ghlmn') == 'abcdedghlmn'
    assert concat('abcdef', '', 'defghl') == 'abcdefghl'

Думаю, это будет довольно быстро:

У вас есть две строки, строка1 и строка2. Посмотрите назад (справа налево) через строку1 на первый символ строки2. Как только у вас будет это положение, определите, есть ли перекрытия. Если нет, вам нужно продолжать поиск. Если есть, вам необходимо определить, есть ли возможность для другого совпадения.

Для этого просто исследуйте более короткую из двух строк на предмет повторения перекрывающихся символов. то есть: если местоположение совпадения в строке1 оставляет короткую оставшуюся строку1, повторите первоначальный поиск с новой начальной точки в строке1. И наоборот, если несовпадающая часть строки 2 короче, ищите в ней повторение перекрывающихся символов.

Повторите, если требуется.

Работа выполнена!

Это не '

Я пытаюсь сделать этот C # как можно более приятным для чтения.

    public static string Concatenate(string s1, string s2)
    {
        if (string.IsNullOrEmpty(s1)) return s2;
        if (string.IsNullOrEmpty(s2)) return s1;
        if (s1.Contains(s2)) return s1;
        if (s2.Contains(s1)) return s2;

        char endChar = s1.ToCharArray().Last();
        char startChar = s2.ToCharArray().First();

        int s1FirstIndexOfStartChar = s1.IndexOf(startChar);
        int overlapLength = s1.Length - s1FirstIndexOfStartChar;

        while (overlapLength >= 0 && s1FirstIndexOfStartChar >=0)
        {
            if (CheckOverlap(s1, s2, overlapLength))
            {
                return s1 + s2.Substring(overlapLength);
            }

            s1FirstIndexOfStartChar = 
                s1.IndexOf(startChar, s1FirstIndexOfStartChar);
            overlapLength = s1.Length - s1FirstIndexOfStartChar;

        }

        return s1 + s2;
    }

    private static bool CheckOverlap(string s1, string s2, int overlapLength)
    {
        if (overlapLength <= 0)
            return false;

        if (s1.Substring(s1.Length - overlapLength) == 
            s2.Substring(0, overlapLength))
            return true;

        return false;            
    }

РЕДАКТИРОВАТЬ: Я вижу, что это почти то же самое, что и решение jerryjvl. Единственная разница в том, что это будет работать с регистром "abcde", "d".

Почему бы просто не сделать что-нибудь нравится. Сначала найдите первый символ или слово (которое будет обозначать перекрытие) в трех столбцах.

Затем начните добавлять первую строку в буфер строки, по одному символу за раз.

Каждый раз смотрите, чтобы увидеть если вы достигли части, которая перекрывается со второй или третьей строкой.

Если да, то начните конкатенацию строки, которая также содержит то, что находится в первой строке.

Когда закончите, начните, если нет перекрытия, начните со второй строка, а затем третья строка.

Итак, во втором примере в вопросе я сохраню d и g в двух переменных.

Затем, когда я добавлю первую строку abc происходит из первой строки, затем я вижу, что d также находится во второй строке, поэтому я перехожу к добавлению из второй строки def добавляются из строки 2, затем я перехожу к строке 3.

Если вы делаете это в базе данных, почему бы просто не использовать для этого хранимую процедуру?

Если вы делаете это вне базы данных, попробуйте perl:

sub concat {
  my($x,$y) = @_;

  return $x if $y eq '';
  return $y if $x eq '';

  my($i) = length($x) < length($y) ?  length($x) : length($y);
  while($i > 0) {
      if( substr($x,-$i) eq substr($y,0,$i) )  {
          return $x . substr($y,$i);
      }
      $i--;
  }
  return $x . $y;
}

Это точно такие же алгоритмы, как и у вас, мне просто любопытно, если java или perl быстрее; -)

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

http://www.algorithmist.com/index.php/Longest_Common_Subsequence