MySQL 最长的公共子字符串

Question

有人有最长公共子字符串（LCS）的MySQL函数吗？ 我在这里找到了一个函数，但在 SQL 中。 作为一名自学成才的程序员，我对MySQL了解不多，但从事语言艺术项目。

Answer 1

MySQL可以说不是实现字符串操作函数的最合适位置，通常我们需要问题来显示对所需代码的一些努力。 我对此有点灵活，因为您至少找到了您要做的事情的参考，并询问MySQL是否具有本机功能。

其实不然。

您还询问是否可以为 MySQL 重写示例代码。

不能。 它似乎依赖于MySQL Server中未实现的功能。

然而。。。这个问题引起了我的兴趣，我喜欢在 MySQL 中做一些不寻常的事情（有时，能够在数据库中做一些事情是很好的，即使它不一定是最有效的地方，有时它可以说是错误的地方，但仍然很方便）......所以今天早上我没有洗澡，而是洗了个澡，在那段时间里，我想出了这个：

DELIMITER $$
DROP FUNCTION IF EXISTS `longest_common_substring` $$
CREATE FUNCTION `longest_common_substring`(short_str TEXT, long_str TEXT) RETURNS text CHARSET utf8
    NO SQL
    DETERMINISTIC
BEGIN
-- http://stackoverflow.com/questions/35545281/mysql-longest-common-substring
DECLARE short_len INT DEFAULT CHAR_LENGTH(short_str);
DECLARE long_len INT DEFAULT CHAR_LENGTH(long_str);
DECLARE swap_str TEXT;
DECLARE max_matched_len INT DEFAULT 0;
DECLARE max_at_left_marker INT DEFAULT NULL;
DECLARE max_at_match_len INT DEFAULT NULL;
DECLARE left_marker INT DEFAULT 0;
DECLARE match_len INT DEFAULT NULL;
IF short_str IS NULL OR long_str IS NULL THEN
  RETURN NULL;
ELSEIF short_str = long_str THEN
  RETURN short_str;
END IF;
IF short_len > long_len THEN
  SET swap_str = long_str;
  SET long_str = short_str;
  SET short_str = swap_str;
  SET short_len = long_len;
  SET long_len = CHAR_LENGTH(long_str);
END IF;
left_loop:
LOOP
  SET left_marker = left_marker + 1;
  IF left_marker + max_matched_len > short_len THEN
    LEAVE left_loop;
  END IF;
  SET match_len = max_matched_len;
  right_loop:
  LOOP
    SET match_len = match_len + 1;
    IF 1 - left_marker + match_len > short_len THEN
      LEAVE right_loop;
    END IF;
    IF long_str LIKE CONCAT ('%',SUBSTRING(short_str FROM left_marker FOR match_len),'%') THEN
      SET max_matched_len = match_len, max_at_left_marker = left_marker;
    ELSE
      LEAVE right_loop;
    END IF;
  END LOOP;
END LOOP;
IF (max_matched_len) THEN
  RETURN SUBSTRING(short_str FROM max_at_left_marker FOR max_matched_len);
ELSE
  RETURN NULL;
END IF;
END $$
DELIMITER ;

它似乎工作正常。

mysql> SELECT longest_common_substring('Lions are growing like yellow roses on the wind','and we turn gracefully in the medieval garden of their roaring blossoms');
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
| longest_common_substring('Lions are growing like yellow roses on the wind','and we turn gracefully in the medieval garden of their roaring blossoms') |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
| n the                                                                                                                                                 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
mysql> SELECT longest_common_substring('die, bart, die','sideshow bob dislikes bart simpson');
+---------------------------------------------------------------------------------+
| longest_common_substring('die, bart, die','sideshow bob dislikes bart simpson') |
+---------------------------------------------------------------------------------+
|  bart                                                                           |
+---------------------------------------------------------------------------------+
1 row in set (0.01 sec)

有一些警告——

如果有多个"最长"子字符串匹配项，

也就是说，如果有两个（或多个）长度完全相同的"最长"子字符串匹配项，则第一个匹配项将是返回的匹配项。

此代码不认为空格或标点符号比其他字符重要，因此在上面的第二个示例中，答案实际上是 5 个字符，' bart'带有前导空格。 可以说，具有 5 个非空格字符的子字符串如果存在，将是更好的匹配，并且此代码不会找到它，因为使用第一个匹配项，除非它们更长，否则不会考虑后续匹配项。 它可以被修改为更复杂的，但这本质上是一个概念证明。

mysql> SELECT longest_common_substring('bart and lisa','bart or lisa');
+----------------------------------------------------------+
| longest_common_substring('bart and lisa','bart or lisa') |
+----------------------------------------------------------+
| bart                                                     |
+----------------------------------------------------------+
1 row in set (0.00 sec)

。但是，如果较短的匹配是候选者，但随后是未连接但较长的匹配，则结果肯定符合预期。

mysql> SELECT longest_common_substring('bart and maggie','bart or maggie');
+--------------------------------------------------------------+
| longest_common_substring('bart and maggie','bart or maggie') |
+--------------------------------------------------------------+
|  maggie                                                      |
+--------------------------------------------------------------+
1 row in set (0.00 sec)

工作原理：

我们采用两个参数，首先期望较短的字符串。 如果较长的字符串是第一个，那很好，因为我们在内存中交换它们，但这会花费我们一点处理时间。

然后，我们将一个临时子字符串（短字符串的一个特制片段）拖到长字符串上，检查长字符串是否为 LIKE % + 我们的临时子字符串 + %。 如果没有，我们转到下一个角色。 如果是这样，我们将临时子字符串扩大 1 个字符，直到我们不再有匹配项 - 但是当我们拥有匹配项时，我们保存了它的位置和长度，并使用此信息作为后续优化，以避免不必要的比较，这些比较不可能产生更好的匹配。

一旦我准备好发布它，我可能会将其添加到我的日期、时间和字符串操作函数集合 https://github.com/sqlbot/dtsl-mysql。