CareerCup

You can build a suffix tree of both strings in O(N) and doing a depth first search, you can find the answer.

Problem :
----------
Return the common string from 2 strings of arrays in optimal running time.


Example/Algo:
------------

S1{tarun}
S2{Varun}


R{arun}

Key Solution :
--------------
Compare the S1 1st char with S2 1st char
if not match then increment J
and continue matching till match is found.

Once match is found increment i & j till i!=j then break.


Code:
---------

Private string Returncommonstrg(String S1 , String S2)
{

For (int i=0 ; i<N-1 ; i++)
{
For (int j=0 ; J<N-1 ; J++)
{
char ch1 = S1[i];
char ch2 = S2[j];

if (Ch1==Ch2)
{
string result += S1[i];
i++;
}

}
}

Return result;

}

Order:
---------
O(N^2)

All that is there is :-
en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

kmp does prefix matching not suffix

This is class dynamic programming problem..pls refer wikipedia for further details