You can build a generalized suffix tree for a set of strings with multiple strings using this implementation. A suffix tree contains all the suffixes of the given text as their keys and positions in the text as their values.
string longestCommonSubstring(const string& str1, const string& str2)
{
if(str1.empty() || str2.empty())
{
return 0;
}
int *curr = new int [str2.size()];
int *prev = new int [str2.size()];
int *swap = NULL;
int maxSubstr = 0;
string longest;
for(unsigned int i = 0; i
The Levenshtein is a measure of how costly it is to adapt a string into another one. If you assign a cost to adding a single character, switching one character for another, and removing a character then you can compute the cost between any two given strings.
Changing a character can be seen as removing a char and adding another one so when adding has cost 1 and removing has cost of one a modification has cost of 2.
The difference between two strings can also be measured in terms of the Levenshtein distance: the distance measure if you think the cost as the “distance” between two strings.
Text comparison is becoming an ever more relevant matter for many fast growing areas such as information retrieval, computational biology, online searching. Levenshtein distance can be used mostly to edit distance, explaining the problem and its relevance.
int levDistance(const std::string source, const std::string target)
{
// Step 1
const int n = source.length();
const int m = target.length();
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
// Good form to declare a TYPEDEF
typedef std::vector > Tmatrix;
Tmatrix matrix(n+1);
// Size the vectors in the 2.nd dimension. Unfortunately C++ doesn't
// allow for allocation on declaration of 2.nd dimension of vec of vec
for (int i = 0; i 2 && j>2) {
int trans=matrix[i-2][j-2]+1;
if (source[i-2]!=t_j) trans++;
if (s_i!=target[j-2]) trans++;
if (cell>trans) cell=trans;
}
matrix[i][j]=cell;
}
}
// Step 7
return matrix[n][m];
}