MySQL最长公共子字符串

Question

有没有人有最长公共子字符串（LCS）的MySQL函数？我发现一个函数here，但在SQL中。作为一名自学成才的程序员，我不太了解MySQL，但是从事与艺术相关的项目。

Answer 1

MySQL可以说并不是实现字符串操作函数的最合适的地方，通常我们需要问题来展示所需代码的一些工作。我对这个有点灵活，因为你至少可以找到你想要做什么的参考，并询问MySQL是否具有本地功能。

它没有。

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

它不能。它似乎依赖于未在MySQL服务器中实现的功能。

但是......这个问题让我很感兴趣，而且我喜欢在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，这是我收集的日期，时间和字符串操作函数，一旦我准备好发布它。