1

问题：

我有 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 函数（测试用例），但是我在编写这个修改后的函数时遇到了麻烦。

4

4 回答 4

1

假设您正在寻找一个模式 *n、*n+2、*n+4 等。并且您有以下字符串：s1="hello 1,bye 2,ciao 1", s2="hello 3,再见 4,ciao 2" 和 s3="你好 5,bye 6,ciao 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"] 作为匹配模式的最长子字符串。

该算法可以通过组合这两个部分并丢弃与模式匹配但次优的早期序列来进一步优化，但为了更清晰，我更喜欢将其分成两部分来呈现。

-- 编辑固定代码块

于 2011-11-13T22:17:13.180 回答
0

写了我自己的解决方案：

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

typedef std::pair<std::pair<std::string, std::string>, std::pair<std::pair<std::string, std::string>, std::pair<std::string, std::string>>> pairStringTrio;
typedef std::pair<std::string,std::pair<std::string,std::string>> stringPairString;

stringPairString longestCommonSubstring(const pairStringTrio&);
std::string strFindReplace(const std::string&, const std::string&, const std::string&);

int main(void) {
        std::string s1= "6 HUMAN ACTIONb", s2="8 HUMAN ACTIONd", s3="10 HUMAN ACTIONf";
        pairStringTrio result = std::make_pair(std::make_pair(s1, "6"), std::make_pair(std::make_pair(s2, "8"), std::make_pair(s3, "10")));

        stringPairString answer = longestCommonSubstring(result);
        std::cout << '\"' << answer.first << "\"\t\"" << answer.second.first << "\"\t\"" << answer.second.second << '\"';
}


stringPairString longestCommonSubstring(const pairStringTrio &foo) {
        std::string longest;

        for(size_t start=0, length=foo.first.first.size()-1; start + length <= foo.first.first.size();) {
                std::string s1_tmp = foo.first.first.substr(start, length);
                std::string s2_tmp = strFindReplace(s1_tmp, foo.first.second, foo.second.first.second);
                std::string s3_tmp = strFindReplace(s1_tmp, foo.first.second, foo.second.second.second);

                if (std::string::npos != foo.second.first.first.find(s2_tmp) && std::string::npos != foo.second.second.first.find(s3_tmp)) {
                        s1_tmp.swap(longest);
                        ++length;
                } else ++start;
        }

        return std::make_pair(longest, std::make_pair(strFindReplace(longest, foo.first.second, foo.second.first.second), strFindReplace(longest, foo.first.second, foo.second.second.second)));
}

std::string strFindReplace(const std::string &original, const std::string& src, const std::string& dest) {
        std::string answer=original;
        for(std::size_t pos = 0; (pos = answer.find(src, pos)) != answer.npos;)
                answer.replace(pos, src.size(), dest);
        return answer;
}
于 2011-11-14T10:56:53.443 回答
0

如果您number1已经知道，并且您知道这些数字在其相应的字符串中只出现一次，那么以下应该有效：

我会打电话给你的字符串s[0]，s[1]等等。设置longest = INT_MAX。对于每个字符串s[i](i >= 0) 只需：

  • 查找 中number1 + 2 * i出现的位置s[i]。假设它发生在位置j。
  • 如果 (i == 0) j0 = j; 别的
    • for (k = 1; k <= j && k <= 最长 && s[i][j - k] == s[0][j0 - k]; ++k) {}
    • 最长 = k;

最后，longest将是所有字符串共有的最长子字符串的长度。

基本上，我们只是从找到数字的点向后扫描，寻找与您的s1(my s[0]) 中相应字符不匹配的情况，并跟踪迄今为止最长匹配的子字符串longest- 这只能保持与我们查看的每个新字符串相同或减少。

于 2011-11-13T18:39:50.487 回答
0

与其尝试修改 LCS 算法的内部结构，不如获取它的输出并在 s1 中找到它。从那里，您的号码将位于输出长度加 1 的偏移量处。

于 2011-11-13T18:46:36.393 回答