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 .
CodePudding user response:
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'
.
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