比较两个字符串的相似程度问题，根据比较的标准常用的可以分为两个子问题：类似与DNA当中两个序列的比较问题和在两个字符串当中取出最长相同子串的问题。
一、DNA问题
DNA问题主要使用动态规划的方法来解决。
DNA问题是这样一个问题，有两个DNA片断d1,d2，为了比较两个DNA片断的相似性我们引进这样一种比较的规则，对于两个DNA片断上面的ATGC序列，我们通过比较从两个片断当中严格按顺序取得一个这样的最长片断，这个片断的每个元素都能够从两个被比较的元素上严格按顺序取下，通过比较这个取下的这个片断的长度来比较两个DNA片断的相似度。例如片断1为GTAGA片断二为GCCTA，那么被取下的片断为GTA，其相似度定义为3。
我们用计算机来解决这个问题的基本思路是，先从结果考虑：设我们取得的片断为r，那么假设r[len] = d1[len] = d2[len]那么就可以推断对于d1和d2这两个片断去掉最后一个元素以后得到的相似片断r'就是在r的基础上去掉最后一个元素；又假设如果d1[len] != d2[len]，那么片断r实质上是d1去掉最后一个元素与d2获得的相似片断和d1与d2去掉最后一个片断获得的相似片断两者之间的较长者。由上面的描述我们可以得到一个LCS函数，LCS函数需要两个片断的当中位置作为参数，其返回一个以两个位置分别作为两个片断的结束点的相似片断，用数学的方式我们可以如下表示：
LCS(i,j) = LCS(i-1,j-1) + 1 d1[i] == d2[j]
LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1)) d1[i] != d2[j]
LCS(i,j) = 0 i == 0 || j == 0
从上面的描述我们可以看到我们所有的推断都是从两个片断的末尾开始的，但是在真正的计算时我们需要从两个片断的开头开始，这是因为从LCS函数我们看到，无论那种情况下如果需要计算必须要知道与i-1或者j-1相关的LCS函数的情况，而对于i == 0或者j == 0的情况我们可以知道LCS的值为0。在程序当中我们使用一张表来记录各个(i,j)组合表示的LCS值，并且用一种形象的方式来记录了最终取得的相似串当中的元素的走向。具体的程序如下：
enum {LEFT,UP,THIS};
struct Node
{
int subLen;
int Router;
};
char * GetSimilar(const char *str1,const char *str2)
{
//Get table
int len1 = strlen(str1);
int len2 = strlen(str2);
Node ** table;
table = new Node * [len1 + 1];
for (int i = 0;i <= len1;i++)
table[i] = new Node[len2 + 1];
//Init table
for (int i = 0;i <= len1;i++)
table[i][0].subLen = 0;
for (int i = 0;i <= len2;i++)
table[0][i].subLen = 0;
//Computer LCS&Router table
for (int i = 1;i <= len1;i++)
for (int j = 1;j <= len2;j++)
{
if (str1[i - 1] == str2[j - 1])
{
table[i][j].subLen = table[i- 1][j - 1].subLen + 1;
table[i][j].Router = THIS;
}
else if (table[i][j - 1].subLen < table[i - 1][j].subLen)
{
table[i][j].subLen = table[i - 1][j].subLen;
table[i][j].Router = UP;
}
else
{
table[i][j].subLen = table[i][j - 1].subLen;
table[i][j].Router = LEFT;
}
}
//use router in table to get similar string (it's inverster)
int minIncream = 50;
int IncreamTime = 0;
char *str = new char[minIncream];
for (int i = 0;i < minIncream;i++)
str[i] = '\\0';
int k = len1,j = len2,pos = 0;
while (k >= 1 && j >= 1)
{
if (table[k][j].Router == THIS)
{
if (strlen(str) + 1 == (IncreamTime + 1) * minIncream)
{
IncreamTime++;
char *t = new char[minIncream * (IncreamTime + 1)];
for (int s = 0;s < minIncream * IncreamTime;s++)
t[s] = str[s];
for (int s = minIncream * IncreamTime;s < minIncream * (IncreamTime + 1);s++)
t[s] = '\\0';
delete[] str;
str = t;
}
str[pos++] = str1[k - 1];
k--;
j--;
}
else if (table[k][j].Router == LEFT)
j--;
else
k--;
}
//inverster string
char *similarStr = new char[strlen(str) + 1];
for (int i = strlen(str) - 1,j = 0;i >= 0;i--,j++)
similarStr[j] = str[i];
similarStr[strlen(str)] = '\\0';
//Clear
for (int i = 0;i <= len1;i++)
delete[] table[i];
delete[] table;
delete[] str;
return similarStr;
}
程序当中的原理可以按照下面的图形象的表示，图当中的一些箭头就是问题解决方案当中描述的解决方式，利用这些箭头我们可以方便的得到最终的相似串。

screen.width-333)this.width=screen.width-333\">

二、最长相同子串问题
最长相同子串问题如果使用枚举的方法从两个子串当中分别取出各种长度相同的子串并进行比较最后从一系列相同子串当中取得最长子串的办法来解决，就从两个字符串当中取子串的子问题就需要2的指数级别的操作，因此在字符串长度较长时性能不能被接受。我们在这里使用了一种类似于上面DNA问题当中的方法来解决这个问题。
首先我们从一个字符开始比较，从将字符串1当中和字符串2当中1个字符相同的两个位置配成位置对并且记录当前已经相同的字符数放入一个链表当中，然后在第二次比较的时候我们根据链表当中已经存在的位置对来比较str1[i+1]和str[j+1]如果相同则把位置对修改为并且将这个链表项当中记录的已经相同的字符数加1，当完成链表当中所有链表项的操作以后我们需要对整个链表进行整理，在链表当中仅仅保留相同字符数量最多的链表项其他链表项都删除，在比较的过程当中如果我们发现所有的链表项当中str1[i+1] != str2[j+1]那么我们可以断定链表当中与保存的信息相关的子串已经是两个字符串之间最长的相同子串，这时比较结束，开始输出这些最长子串，具体算法如下：
struct Node
{
int pos1;
int pos2;
int len;
Node *next;
};
struct Queue
{
Node *front;
Node *rear;
int maxLen;
};
void InitQueue(Queue &q);
void InsertQueue(Queue &q,int len,int pos1,int pos2);
void DeleteQueue(Queue &q);
void OrderQueue(Queue &q);
void EmptyQueue(Queue &q);

char *GetMaxSub(const char *str1,const char *str2);

void InitQueue(Queue &q)
{
q.front = q.rear = 0;
q.maxLen = -1;
}
void InsertQueue(Queue &q,int len,int pos1,int pos2)
{
Node *node = new Node;
node->pos1 = pos1;
node->pos2 = pos2;
node->len = len;
node->next = 0;
if (len > q.maxLen)
q.maxLen = len;
if (q.front == 0)
q.front = node;
else
q.rear->next = node;
q.rear = node;
}
void DeleteQueue(Queue &q)
{
if (q.front)
{
Node *temp = q.front;
q.front = q.front->next;
if (temp == q.rear)
q.rear = 0;
delete temp;
}
}
void OrderQueue(Queue &q)
{
Node *node = q.front;
Node *preNode = 0;
while (node)
{
if (node->len > q.maxLen)
q.maxLen = node->len;
node = node->next;
}
node = q.front;
while (node)
if (node->len < q.maxLen)
{
if (preNode == 0)
{
DeleteQueue(q);
node = q.front;
}
else
{
preNode->next = node->next;
if (node == q.rear)
q.rear = preNode;
Node *temp = node;
node = node->next;
delete temp;
}

}
else
{
preNode = node;
node = node->next;
}
}
void EmptyQueue(Queue &q)
{
while (q.front)
DeleteQueue(q);
}
char * GetMaxSub(const char *str1,const char *str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
Queue q;
InitQueue(q);
for (int i = 0;i < len1;i++)
for (int j = 0;j < len2;j++)
if (str1[i] == str2[j])
InsertQueue(q,0,i,j);
int curLen;
do
{
curLen = q.maxLen;
Node *node = q.front;
while (node)
{
if (node->pos1 + node->len + 1 < len1 && node->pos2 + node->len + 1 < len2 && str1[node->pos1 + node->len + 1] == str2[node->pos2 + node->len + 1])
node->len++;
node = node->next;
}
OrderQueue(q);
}while (curLen < q.maxLen);

char *returnvalue = 0;
if (q.front)
{
returnvalue = new char[q.maxLen + 2];
strncpy(returnvalue,&str1[q.front->pos1],q.front->len + 1);
returnvalue[q.front->len + 1] = '\\0';
}
EmptyQueue(q);
return returnvalue;
}