SPOJ 1021. Aibohphobia

This is the problem statement
http://www.spoj.com/problems/AIBOHP/

This problem is similar to the problem Palindrom 2000 (IOIPALIN). This task can be turned into another task. The number of insertions equals to the length of the string minus LCS(longest common subsequence) of the given string and the reversed string of the given string.
formula
answer=n - LCS( string, reversed string)

You can find information about LCS here.

DOWNLOAD FULL SOURCE CODE

SPOJ 7150. Palindrome 2000

Th statement of the task
http://www.spoj.com/problems/IOIPALIN/

his task can be solved by looking at it from different point of view. We can easily turn this task into a classic LCS (longest common subsequence algorithm). This will be the formula for finding out answer
answer= n- LCS(given string, reversed string of the given string)

You can find about finding the LCS here.

NOTE: I was getting TLE many times because of a simple problem. LCS has n^2 complexity, It is perfectly fine because 5000^2 will fit in 1 second but there is one problem. The LCS algorithm suggests to keep a matrix of NxN when the matrix gets full the processor runs slower that is why you may get TLE. For this you need to do a simple trick. We don't need to keep the whole 5000x5000 array. In every step. When we are at the row I, we use only the row I and I-1 . So instead of keeping 5000x5000 array we can keep only 2x2000 array and solve it there.

DOWNLOAD THE FULL SOURCE CODE

Minimum insertions to turn the string into palindrome

This task can be easily brought to another task of finding the length of the string minus the Longest Common subsequence of the given string and the reversed string of the given string.

In other words our answer will look like this

answer= n- LCS(s, reversed s);  ////n is the length of our string

Infomration about finding LCS can be found here

LCS(longest common subsequence)

As we all know dynamic programming works like this.
1. Divide the big problem into smaller subproblems.
2. Solve the current subproblem with the use of previously found solutions.

We have 2 arrays of char char s1[N],s2[N]; and we want to find the longest common subsequence of those strings.
For finding the longest common subsequence we will keep an 2 dimensional array (matrix) int a[N][N]
and a[i][j] will show us the length of the longest common subsequence of  sequences
s1[1],s1[2],....,s1[i]
                         and
s2[1],s2[2],....,s2[j]

This is the pseudocode of our algorithm

for i =from 1 to n    ////n is the length of the first sequence
for j =from 1 to m   ////m is the length of the second sequence
if(s1[i]==s2[j])
       a[i][j]=a[i-1][j-1]+1
else
       a[i][j]max(a[i-1][j],a[i][j-1]);
Example with explanation

	S	R	J	M
T	0	0	0	0
S	1	1	1	1
R	1	2	2	2
M	1	2	2	3

Suppose we have 2 strings s1="SRJM" and s2="TSRM"
a[1][1] shows the longest common subsequence for 2 strings "T" and "S", the string letter "T" is not equal to the letter "S" so we mark a[1][1] as 0. The same goes for the letters "R" "J" and "M"

lets get down to a[2][1]  . a[2][1] shows us the longest common subsequence of strings "TS" and "S"
as we can see we marked it as 1. The pseudocode says if s[i]==s[j] then a[i][j]=a[i-1][j-1]+1; =>
=>a[2][1]=a[1][0]+1 (All the elements are marked as 0 from the beginning)
Now we are at the cell a[2][2] which means that we need to look at 2 strings "TS" and "SR" . The letter "S" is not equal to letter "R" which means that we have to pick up the value of the longest common subsequence of either "T" and "SR" or "TS" and "S" . The second option has bigger value that is why we pick the second option which is a[i][j-1];

The full source code is also available for free download

DOWNLOAD THE SOURCE CODE 

IF YOU HAVE ANY QUESTIONS LEAVE THEM IN COMMENTS , NO QUESTION WILL STAY UNANSWERED