在 S1 中找到 S2 的最长公共起始子串

Question

我正在解决一个问题。我在S1部分解决了S2的Longest Common starting substring但是时间复杂度很高

在下面的代码中，我必须在 s[i].
中找到 str3 的最长公共起始子串在下面的代码中，我也使用了 KMP 算法而不是查找函数，但我再次面临高时间复杂度。

 string str3=abstring1(c,1,2,3);
                while(1)
                {
                    size_t found = s[i].find(str3);
                    if(str3.length()==0)
                        break;
                    if (found != string::npos)
                    {
                        str1=str1+str3;
                        break;
                    }
                    else
                    {
                        str3.pop_back();
                    }
                }

示例：
S1=balling S2=baller
ans=球
S1=balling S2=uolling
ans=

我们必须在 S1
中找到 S2 的公共起始子串你能帮忙写c++吗
我找到了 Similar Post 但我无法用 C++ 做我自己。

Answer 1

这是一种散发出淡淡的黑客香气的解决方案。

假设

s1 = 'snowballing'
s2 = 'baller'

然后形成字符串

s = s2 + '|' + s1
  #=> 'baller|snowballing'

竖线 ('|') 可以是不在任一字符串中的任何字符。（如果有疑问，可以使用 "\x00"。）

然后我们可以将 s 与正则表达式

进行匹配

^(.*)(?=.*\|.*)

这将匹配 s2 中出现在 s1 中的最长起始字符串，在本例中为 'ball'.

Demo

正则表达式可以分解如下

^        # match beginning of string
(        # begin capture group 1
  .*     # match zero or more characters, as many as possible
)        # end capture group 1
(?=      # begin a positive lookahead
  .*     # match zero or more characters, as many as possible 
  \|     # match '|'
  .*     # match zero or more characters, as many as possible 
       # match the contents of capture group 1
)        # end positive lookahead

在 S1 中找到 S2 的最长公共起始子串

Find the Longest Common starting substring of S2 in S1

c++

regex

string

data-structures