检查2个字符串中是否有公共子字符串c ++

Question

我已经做了解决方案，但我需要一个优化的方案。任务是：

读取两个字符串
获取第一个字符串的每个子字符串并在第二个字符串中找到每个子字符串
如果存在，打印"yes"，否则打印"no"

我已经做出的解决方案：

int check(string A, string B)
{ 
    string s3;
    int flag=0 ,len1,len2,k=0;
    s3[0]='[=10=]';
    cin>>A>>B;
    len1=A.length();
    len2=B.length();

    for(int i=0;i<len1;i++)
    {
        k=len1-i;

        for(int j=1;j<k;j++ )
        {
            s3=A.substr(i,j);

            size_t found=B.find(s3);

            if(found!=string::npos)
            { 
                flag=1;
                return flag;
            }

        } 
    }
}

Answer 1

bool check(const std::string & a, const std::string & b) {
   return b.find_first_of(a) != std::string::npos;
}

你看，如果字符串 b 不包含来自 a 的大小为 1 的子字符串，它就不能包含以相同符号开头的更大的子字符串。所以你基本上只需要检查字符串 b 是否包含字符串 a.

中的任何符号

Answer 2

除了优化解决方案，您的代码还有其他问题。例如，并非所有代码路径 return 一个值。

最有效的解决方案取决于许多因素，包括两个字符串的大小、两个字符串的匹配程度等。

如果没有这些信息，我建议您可以使用：

从第二个字符串

trie

从第一个字符串

suffix array

使用后缀数组生成第二个字符串的所有子字符串。随着生成检查其在步骤 1 中创建的 trie 中是否存在。

您可以考虑的其他方法包括修改 rabin karp，这应该不难理解。

Answer 3

将第一个字符串的所有字符放入哈希集中(unordered_set)，然后遍历第二个字符串的字符并检查哈希集中是否存在它们。如果是，则存在一个公共子串（至少长度为 1）否则，没有公共子串。

检查2个字符串中是否有公共子字符串c ++

To check if there is a common substring in 2 strings c++

c++

string

algorithm

substring

find