Find the Longest Common starting substring of S2 in S1

Question

I was solving a problem. i solved the Longest Common starting substring of S2 in S1 part but the time complexity was very high.

In the below Code I have to find the Longest Common starting substring of str3 in s[i].
In the below code instead of find function i have also use KMP algorithm but i faced high time complexity again.

 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();
                    }
                }

Example :
S1=balling S2=baller
ans=ball
S1=balling S2=uolling
ans=


We have to find common starting substring of S2 in S1
Can you help in c++
I find Similar Post but i was not able to do my self in c++.

Answer 1

Here is a solution that emits the faint aroma of a hack.

Suppose

s1 = 'snowballing'
s2 = 'baller'

Then form the string

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

where the pipe ('|') can be any character that is not in either string. (If in doubt, one could use, say, "\x00".)

We may then match s against the regular expression

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

This will match the longest starting string in s2 that is present in s1, which in this example is 'ball'.

Demo

The regular expression can be broken down as follows.

^        # 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