@arun , topcoder
As i have mentioned above we need to also include (0,0) and (N, N)
Also, 0th index is inclusive while adding the chars from RevStr...
i.e *We will insert RevStr(yi .. y i+1) , excluding the extreme chars*
if yi = 0 , then RevStr [0 yi +1)
Now, its obvious that when you get the following notation then no
chars would be considered:
[ 0 , 0 )
As the example that you have generated is based on 1-based indexing
the above coordinates shall be modified to (1,1) and (N+1,N+1)
Hence,
LCS exact pairs would be (1,1) , (2,2) , (3,3) , (4,4) , (6,6) ... as
N = 5 for 'dabae'
Now as per the explanation:
Index 1 2 3 4 5
OStr = D A B A E
RStr = E A B A D
// Just before
// xi +1 // (yi, yi
+1)
X(i) Y(i) X(i+1) Y(i+1) OrigStrInd RevStrIndRange
1 1 2 2 2 [1, 2)
2 2 3 3 3 (2,
3)
3 3 4 4 4 (3, 4)
4 4 6 6 6 (4, 6)
OrigStrInd RevStrIndRange RevStrIncluded
2 [1, 2) E
3 (2, 3) null
4 (3, 4) null
5 (4, 6) D
Iteration ResultantStr
1 D (E) A B A E
2 D (E) A(null) B A E
3 D (E) A(null) B (null) A E
4 D (E) A(null) B (null) A E (D)
All the elements in brackets are the inserted strings..
Null is nothing but denotes that there is nothing to insert..
Hence, final string : DEABAED ...
On Jan 2, 8:12 pm, top coder <[email protected]> wrote:
> @Lucifer
>
> As per the LCS for example "dabae"
>
> Reverse String is "eabad"
>
> e a b a d
>
> 0 0 0 0 0 0 0
>
> d 0 0 0 0 0 1
>
> a 0 0 1 1 1 1
>
> b 0 0 1 2 2 2
>
> a 0 0 1 2 3 3
>
> e 0 1 1 2 3 3
>
> LCS Exact Pairs: (2,2),(3,3) (4,4)
>
> Could you please explain your algo with this example:?
>
> On Jan 2, 7:26 pm, Arun Vishwanathan <[email protected]> wrote:
>
>
>
>
>
>
>
>
>
> > @lucifer: can you please give a small example and explain?
> > "
> > Now, all we need to do is sequentially access the list and do the
> > following:
> > Given 2 pairs (xi, yi) and (x i+1, y i+1),
> > We will insert RevStr(yi .. y i+1) , excluding the extreme chars, just
> > before Str(x i+1)..."
>
> > On Fri, Dec 16, 2011 at 4:26 AM, atul anand <[email protected]> wrote:
> > > Ignore my previous comment
>
> > > On 16 Dec 2011 17:35, "atul anand" <[email protected]> wrote:
>
> > > > @All : can't we use Levenshtein algorithm to find min
> > > addition/deletion.??
>
> > > > On Fri, Dec 16, 2011 at 2:50 PM, top coder <[email protected]> wrote:
>
> > > >> @Lucifer
>
> > > >> I have got the intent of your logic.
>
> > > >> From the algo, We got to know how many characters need to be added.
> > > >> How do you concluded where do you need to add the characters exactly
> > > >> and What characters needs to be added?
> > > >> Also Could you comment on the time and space complexity?
>
> > > >> On Dec 15, 11:37 am, Lucifer <[email protected]> wrote:
> > > >> > Correction:
>
> > > >> > for NAN :
> > > >> > N(IT)A + TI + N = NITATIN
>
> > > >> > On Dec 15, 11:33 am, Lucifer <[email protected]> wrote:
>
> > > >> > > @topcoder..
>
> > > >> > > String: NITAN
>
> > > >> > > RevStr: NATIN
>
> > > >> > > LCS ( NITAN, NATIN) = { NIN , NAN }
>
> > > >> > > Here all we care about the count which is 2. Hence, 2 additions
> > > would
> > > >> > > be required to convert it into a palindrome..
>
> > > >> > > The possible palindromes would be:
> > > >> > > for NIN :
> > > >> > > N + AT + I(TA)N = NATITAN
>
> > > >> > > for NAN :
> > > >> > > N + TI+ A(IT)N = NATITAN
>
> > > >> > > On Dec 15, 11:24 am, top coder <[email protected]> wrote:
>
> > > >> > > > @Mohit
>
> > > >> > > > Suppose for example
>
> > > >> > > > String: NITAN
> > > >> > > > LCS(Longest Common Subsequence) : NIN
>
> > > >> > > > How do you get the palindrome with it?
>
> > > >> > > > On Dec 15, 3:47 am, Lucifer <[email protected]> wrote:
>
> > > >> > > > > @Mohit
>
> > > >> > > > > I think what he meant is 2* strlen("Input String") - 2*
> > > ("Length of
> > > >> > > > > LCS")
>
> > > >> > > > > On Dec 15, 3:44 am, Mohit kumar lal <[email protected]>
> > > wrote:
>
> > > >> > > > > > @saurabh-as by the above example LCS of "HELLO" and its
> > > inverse would be
> > > >> > > > > > "LL" and how can we form the word "HELLOLLEH" with it ...
> > > >> > > > > > and is your ans for the word "NITAN" is "NITATIN" ...?
>
> > > >> > > > > > On Wed, Dec 14, 2011 at 8:39 PM, saurabh singh <
> > > [email protected]> wrote:
> > > >> > > > > > > Find the LCS of string with its reverse....
>
> > > >> > > > > > > On Wed, Dec 14, 2011 at 8:33 PM, top coder <
> > > [email protected]> wrote:
>
> > > >> > > > > > >> Given a word, convert it into a palindrome with minimum
> > > addition of
> > > >> > > > > > >> letters to it. letters can be added anywhere in the word.
>
> > > >> > > > > > >> . for eg if hello is given, result should be hellolleh
>
> > > >> > > > > > >> --
> > > >> > > > > > >> You received this message because you are subscribed to
> > > the Google Groups
> > > >> > > > > > >> "Algorithm Geeks" group.
> > > >> > > > > > >> To post to this group, send email to
> > > [email protected].
> > > >> > > > > > >> To unsubscribe from this group, send email to
> > > >> > > > > > >> [email protected].
> > > >> > > > > > >> For more options, visit this group at
> > > >> > > > > > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > >> > > > > > > --
> > > >> > > > > > > Saurabh Singh
> > > >> > > > > > > B.Tech (Computer Science)
> > > >> > > > > > > MNNIT ALLAHABAD
>
> > > >> > > > > > > --
> > > >> > > > > > > You received this message because you are subscribed to the
> > > Google Groups
> > > >> > > > > > > "Algorithm Geeks" group.
> > > >> > > > > > > To post to this group, send email to
> > > [email protected].
> > > >> > > > > > > To unsubscribe from this group, send email to
> > > >> > > > > > > [email protected].
> > > >> > > > > > > For more options, visit this group at
> > > >> > > > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > >> > > > > > --
> > > >> > > > > > Mohit kumar lal
> > > >> > > > > > rit2009014
> > > >> > > > > > IIIT ALLAHABAD
> > > >> > > > > > contact@9454681805
> > > >> > > > > > [email protected]
> > > >> > > > > > [email protected]
> > > >> > > > > > [email protected]://
> > > profile.iiita.ac.in/rit2009014-Hidequotedtext -
>
> > > >> > > > > - Show quoted text -- Hide quoted text -
>
> > > >> > - Show quoted text -
>
> > > >> --
> > > >> You received this message because you are subscribed to the Google
> > > Groups "Algorithm Geeks" group.
> > > >> To post to this group, send email to [email protected].
> > > >> To unsubscribe from this group, send email to
> > > [email protected].
> > > >> For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > "People often say that motivation doesn't last. Well, neither does bathing
> > - that's why we recommend it daily."- Hide quoted text -
>
> > - Show quoted text -
>
> On Jan 2, 7:26 pm, Arun Vishwanathan <[email protected]> wrote:
>
>
>
>
>
>
>
> > @lucifer: can you please give a small example and explain?
> > "
> > Now, all we need to do is sequentially access the list and do the
> > following:
> > Given 2 pairs (xi, yi) and (x i+1, y i+1),
> > We will insert RevStr(yi .. y i+1) , excluding the extreme chars, just
> > before Str(x i+1)..."
>
> > On Fri, Dec 16, 2011 at 4:26 AM, atul anand <[email protected]> wrote:
> > > Ignore my previous comment
>
> > > On 16 Dec 2011 17:35, "atul anand" <[email protected]> wrote:
>
> > > > @All : can't we use Levenshtein algorithm to find min
> > > addition/deletion.??
>
> > > > On Fri, Dec 16, 2011 at 2:50 PM, top coder <[email protected]> wrote:
>
> > > >> @Lucifer
>
> > > >> I have got the intent of your logic.
>
> > > >> From the algo, We got to know how many characters need to be added.
> > > >> How do you concluded where do you need to add the characters exactly
> > > >> and What characters needs to be added?
> > > >> Also Could you comment on the time and space complexity?
>
> > > >> On Dec 15, 11:37 am, Lucifer <[email protected]> wrote:
> > > >> > Correction:
>
> > > >> > for NAN :
> > > >> > N(IT)A + TI + N = NITATIN
>
> > > >> > On Dec 15, 11:33 am, Lucifer <[email protected]> wrote:
>
> > > >> > > @topcoder..
>
> > > >> > > String: NITAN
>
> > > >> > > RevStr: NATIN
>
> > > >> > > LCS ( NITAN, NATIN) = { NIN , NAN }
>
> > > >> > > Here all we care about the count which is 2. Hence, 2 additions
> > > would
> > > >> > > be required to convert it into a palindrome..
>
> > > >> > > The possible palindromes would be:
> > > >> > > for NIN :
> > > >> > > N + AT + I(TA)N = NATITAN
>
> > > >> > > for NAN :
> > > >> > > N + TI+ A(IT)N = NATITAN
>
> > > >> > > On Dec 15, 11:24 am, top coder <[email protected]> wrote:
>
> > > >> > > > @Mohit
>
> > > >> > > > Suppose for example
>
> > > >> > > > String: NITAN
> > > >> > > > LCS(Longest Common Subsequence) : NIN
>
> > > >> > > > How do you get the palindrome with it?
>
> > > >> > > > On Dec 15, 3:47 am, Lucifer <[email protected]> wrote:
>
> > > >> > > > > @Mohit
>
> > > >> > > > > I think what he meant is 2* strlen("Input String") - 2*
> > > ("Length of
> > > >> > > > > LCS")
>
> > > >> > > > > On Dec 15, 3:44 am, Mohit kumar lal <[email protected]>
> > > wrote:
>
> > > >> > > > > > @saurabh-as by the above example LCS of "HELLO" and its
> > > inverse would be
> > > >> > > > > > "LL" and how can we form the word "HELLOLLEH" with it ...
> > > >> > > > > > and is your ans for the word "NITAN" is "NITATIN" ...?
>
> > > >> > > > > > On Wed, Dec 14, 2011 at 8:39 PM, saurabh singh <
> > > [email protected]> wrote:
> > > >> > > > > > > Find the LCS of string with its reverse....
>
> > > >> > > > > > > On Wed, Dec 14, 2011 at 8:33 PM, top coder <
> > > [email protected]> wrote:
>
> > > >> > > > > > >> Given a word, convert it into a palindrome with minimum
> > > addition of
> > > >> > > > > > >> letters to it. letters can be added anywhere in the word.
>
> > > >> > > > > > >> . for eg if hello is given, result should be hellolleh
>
> > > >> > > > > > >> --
> > > >> > > > > > >> You received this message because you are subscribed to
> > > the Google Groups
> > > >> > > > > > >> "Algorithm Geeks" group.
> > > >> > > > > > >> To post to this group, send email to
> > > [email protected].
> > > >> > > > > > >> To unsubscribe from this group, send email to
> > > >> > > > > > >> [email protected].
> > > >> > > > > > >> For more options, visit this group at
> > > >> > > > > > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > >> > > > > > > --
> > > >> > > > > > > Saurabh Singh
> > > >> > > > > > > B.Tech (Computer Science)
> > > >> > > > > > > MNNIT ALLAHABAD
>
> > > >> > > > > > > --
> > > >> > > > > > > You received this message because you are subscribed to the
> > > Google Groups
> > > >> > > > > > > "Algorithm Geeks" group.
> > > >> > > > > > > To post to this group, send email
>
> ...
>
> read more »
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
