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++.

Because it's mandatory to consider starting of S2 starting letters are uo — Yash, May 03 '22 at 04:28
@CarySwoveland you can also check the similar post .. i have mentioned the link in last — Yash, May 03 '22 at 04:51

Cary Swoveland · Accepted Answer · 2022-05-03T08:13:07.903

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

This is what I want. But can you help me doing the same thing for c++ — Yash, May 03 '22 at 08:59
Sorry, but I don't speak C++. Perhaps a reader can help. The C++ code should be short and sweet. — Cary Swoveland, May 03 '22 at 13:53

Find the Longest Common starting substring of S2 in S1

1 Answers1