c++ - 受模式约束的最长公共(public)子串

Question

问题:

我有 3 个字符串 s1、s2、s3。每个都在两边包含垃圾文本，在其中心有一个定义模式:text1+number1。 number1 在每个字符串中增加 2。我想提取 text1+number1。

我已经编写了代码来查找number1

我如何扩展 LCS 函数来获取 text1？

#include <iostream>

const std::string longestCommonSubstring(int, std::string const& s1, std::string const& s2, std::string const& s3);

int main(void) {
    std::string s1="hello 5", s2="bolo 7", s3="lo 9sdf";
    std::cout << "Trying to get \"lo 5\", actual result: \"" << longestCommonSubstring(5, s1, s2, s3) << '\"';
}

const std::string longestCommonSubstring(int must_include, std::string const& s1, std::string const& s2, std::string const& s3) {
    std::string longest;

    for(size_t start=0, length=1; start + length <= s1.size();) {
        std::string tmp = s1.substr(start, length);
        if (std::string::npos != s2.find(tmp) && std::string::npos != s3.find(tmp)) {
            tmp.swap(longest);
            ++length;
        } else ++start;
    }

    return longest;
}

---

示例:

从 "hello 5", "bolo 7", "lo 9sdf" 我想得到 "lo 5 "

代码:

我已经能够编写一个简单的 LCS 函数(test-case)，但是我在编写这个修改后的函数时遇到了问题。

Answer 1

假设您要查找模式 *n、*n+2、*n+4 等。您有以下字符串:s1="你好 1，再见 2，再见 1"，s2="你好 3，再见 4，再见 2"和 s3="你好 5，再见 6，再见 5"。然后执行以下操作:

//find all pattern sequences
N1 = findAllPatterns(s1, number);
 for i = 2 to n:
  for item in Ni-1:
   for match in findAllPatterns(si, nextPattern(item))
    Ni.add([item, (match, indexOf(match))]);

//for all pattern sequences identify the max common substring
maxCommonLength = 0; 
for sequence in Nn:
 temp = findLCS(sequence);
 if(length(temp[0]) > maxCommonLength):
  maxCommonLength = length(temp[0]);
  result = temp;

return result;

`算法的第一部分将识别序列:[(1, 6), (3, 6), (5, 6)], [(1, 19), (3, 6), (5, 6)], [(2, 12), (4, 12), (6, 12)]

第二部分将确定:["hello 1", "hello 3", "hello 5"] 作为与模式匹配的最长子串。

可以通过组合这两部分并丢弃与模式匹配但次优的早期序列来进一步优化算法，但为了更清楚起见，我更愿意将其分为两部分。

-- 编辑固定代码块