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

Question

我正在解决一个问题。我在S1部分解决了S2的最长公共起始子串，但时间复杂度非常高

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

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=ball
S1=balling S2=uolling
ans=


我们必须在S1中找到S2的常用起始子串
你能在c++中帮忙吗
我找到了类似的Post，但我无法在c++中完成自己的工作。

Answer 1

这里有一个能散发出淡淡黑客香气的解决方案。

假设

s1 = 'snowballing'
s2 = 'baller'

然后形成字符串

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

其中管道('|')可以是不在任一字符串中的任何字符。(如果有疑问，可以使用"x00"。)

然后，我们可以将s与正则表达式进行匹配

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

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

演示

正则表达式可以分解如下。

^        # 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 
1     # match the contents of capture group 1
)        # end positive lookahead