Hirschberg’s linear space algorithm in C++
Posted on August 4, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
It should work on any container type which supports forward and reverse iteration. It’s similar to the Python implementation, but note:
rather than copy slices of the original sequences, it passes around iterators and reverse iterators into these sequences rather than recursively accumulating sums of sub-LCS results, it ticks off items in a members array, xs_in_lcs /\* C++ implementation of "A linear space algorithm for computing maximal common subsequences" D.
[Read More]Hirschberg's algorithm
Posted on August 4, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Hirschberg’s algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the least cost sequence alignment between two strings, where cost is measured as Levenshtein edit distance, defined to be the sum of the costs of insertions, replacements, deletions, and null actions needed to change one string to the other. Hirschberg’s algorithm is simply described as a divide and conquer version of the Needleman-Wunsch algorithm.
The Needleman-Wunsch algorithm finds an optimal alignment in O(nm) time, using O(nm) space.
[Read More]Dynamic Programming Algorithm (DPA) for Edit-Distance
Posted on August 3, 2010
(Last modified on August 7, 2020)
| 7 minutes
| Kinshuk Chandra
The words `computer’ and `commuter’ are very similar, and a change of just one letter, p->m will change the first word into the second. The word `sport’ can be changed into `sort’ by the deletion of the `p’, or equivalently, `sort’ can be changed into `sport’ by the insertion of `p’.
The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of:
[Read More]Longest common substring problem
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Given two sequences of letters, such as A = HELLO and B = ALOHA,
find the longest contiguous sequence appearing in both.
**One solution: ** (assume strings have lengths m and n)
For each of the m starting points of A, check for the longest common string starting at each of the n starting points of B.
The checks could average Θ(m) time → a total of Θ(m^2*n) time.
Dynamic programming solution:
[Read More]Longest common subsequence : Dynamic programming
Posted on April 26, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
m: A B C B D A B
yn: B D C A B A
The LCS is B C B A
For arbitrary inputs, it is NP-hard. For constant inputs, DP gives the solution in polynomial time ex: O(n^k). Also, there can be more than one LCSs and the solution for that is exponential time ex: O(k^n).
Here we maintain an LCS matrix of m*n size. Initially, for i= 0 or j = 0, LCSij = 0.
[Read More]String matching
Posted on April 26, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The naive brute force approach:
It is very simple to code but there are little things to look for (as least I have to) with respect to optimization. The outer loop runs for text, the inner loop runs for pattern with one more condition - **i+ len(pattern) <= len(text)**.
int bruteForce (text, pattern) for (i =0; i < len(text); i++):
for (j = 0; j < len(pattern) && **i+ len(pattern) <= len(text)**; j++): //instead of i+j < len(text) if text[i+j] !
[Read More]Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine? (eg given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false)
Posted on April 10, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
**Syntax of strstr** const char * strstr ( const char * str1, const char * str2 );
Returns a pointer to the first occurrence of _str2_ in _str1_, or a null pointer if _str2_ is not part of _str1_. The matching process does not include the terminating null-characters. **Approach1** Append str1 to itself and do a strstr for str2. That should work. (I am assuming strstr looks for string x within string y).
[Read More]WAP to check whether string is palindrome
Posted on December 5, 2009
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Write a method which will accept a string and return true if the string is a palindrome and false if it isn’t.
Follow up:
a) your method should consider lower case and upper case characters to be the same.
b) your method should ignore special characters and white spaces, for e.g. if your input were the strings were “Madam, I’m Adam!!”, then you should consider it a palindrome and hence return true ignoring case and special characters.
[Read More]Given two strings A and B, how would you find out if the characters in B were a subset of the characters in A?
Posted on December 5, 2009
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Here is a code in c:
#include <stdio .h> #include <conio .h> int isSubset(char \*a, char \*b); int main(){ char str1\[\]="defabc"; char str2\[\]="abcfed"; if(isSubset(str1, str2)==0) printf("\\nYes, characters in B=\[%s\] are a subset of characters in A=\[%s\]\\n",str2,str1); } else { printf("\\nNo, characters in B=\[%s\] are not a subset of characters in A=\[%s\]\\n",str2,str1); } getch(); return(0); } // Function to check if characters in "b" are a subset // of the characters in "a" int isSubset(char \*a, char \*b) { int letterPresent\[256\]; int i; for(i=0; i<256; i++) letterPresent\[i\]=0; for(i=0; a\[i\]!
[Read More]String Class in cpp(Standard cpp strings)
Posted on August 18, 2008
(Last modified on August 7, 2020)
| 27 minutes
| Kinshuk Chandra
Here is how to test the string class already present in cpp.
To use simple strings u have to include . For example consider the program,
#include #include <conio.h>
using namespace std;
int main()
{
string word="hello”;
cout«word;
getch();
}
There are various functions and operators in this string class. These operators are present in string -
= assignment
+ , += concatenation etc
== , != . < , <= , >= , > equality etc.
[Read More]