字符串匹配(1) - 近似串匹配

    近似串就是并非完全相同的串(如happy和hsppy，或者pattern和patern)，它们之间或者有字母不同，或者少掉一些字母，或者多一些字母。定义近似串之间的差别数为通过“修改，删去 或者 插入”使两串达到完全一致的操作次数。如aproxiomally与approximatly之间的差别数就是3。近似串匹配就是一种特殊的模式匹配--找到与模式差别数最少的子串。差别数为0，就退化为普通的串模式匹配问题。
    问题用动态规划解决。定义差别函数D(i,j)(0<=i<=m, 0<=j<=n)表示样本前缀子串p1,...,pi与文本前缀子串t1,...,tj之间的最小差别数，则D(m,n)表示样本P与文本T的最小差别数。当p1,...,pi与t1,...,tj对应时，D(i,j)有四种情况：
1) 字符pi与tj对应且pi=tj，此时对应差别数为D(i-1,j-1);
2) 字符pi与tj对应且pi!=tj，此时对应差别数为D(i-1,j-1)+1;
3) 字符pi多余，即pi对应于tj后的空，则对应差别数为D(i-1,j)+1;
4）字符tj多余，即pi对应于t(j-1)，则对应差别数为D(i,j-1)+1;
所以，递推关系可如下表示(D矩阵大小为(m+1)x(n+1),第一行与第一列为padding，起重要作用)：
当pi=tj时，D(i,j)=min(D(i-1,j-1), D(i-1,j)+1, D(i,j-1)+1);
当pi!=tj时，D(i,j)=min(D(i-1,j-1)+1, D(i-1,j)+1, D(i,j-1)+1);
初始值设置如下：
1) D(0,j) = 0;
2) D(i,0) = i;
    特别注意，D(0,j)的设置与递推关系一样，是本方法的两个最重要的关键点。D(0,j)设置为0表明计算差别数时t1,...,tj中前面一部分是不算进去的，即差别数只是统计了t_k,...,tj的部分(这里k为某一值)！举个例子，如求D[1][10]时(假设p1=t10), D[0][9]为0，从第9或第10个字母起开始统计代价，关键关键！！

---

程序代码如下：

int mymin(int& index, int a, int b, int c)
{
 int min = a;
        index = 1;
 if (min > b){
     min = b; index = 2;
 }
 if (min > c){
     index = 3;
     min = c;
 }
 return min;
}

// 递归打印匹配的近似子串
void print_pat_match(string& text, int** dirt, int i, int j)
{
 if (i<0 || j<0)  // boundary
  return;
 
 if (dirt[i][j] == 1) {       // 1代表此处pi与tj是对应的
  print_pat_match(text, dirt, i-1, j-1);
  cout << text[j];
 }
 else if (dirt[i][j] == 2){   // 2代表往上，即pi对应空，或者说pi是多出的
  print_pat_match(text, dirt, i-1, j);
 }
 else{                        // 3代表往左，即tj对应空，或者说tj是多出的
  print_pat_match(text, dirt, i, j-1);
 }
}

int approx_match(string& text, string& pat)
{
 int m = pat.size();          // 模式串长度
 int n = text.size();         // 文本串长度
 int i,j;
 int** cost = new int*[m+1];  // 代价表
 for (i = 0; i <= m; ++i)
     cost[i] = new int[n+1];
 
 int** dirt = new int*[m];  // 用于追踪匹配时的选择，值为1，2或者3，代表3方向
 for (i = 0; i < m; ++i)
     dirt[i] = new int[n];
 for (i = 0; i < m; i++)
     for (j = 0; j < n; j++)
  dirt[i][j] = 0;
 
 for (j = 0; j <= n; ++j) //  代价初始化
  cost[0][j] = 0;
 for (i = 0; i <= m; ++i)
  cost[i][0] = i;

 int index;   int min_n = n, min_cost=100;
 // 动态规划
 for (i = 1; i <= m; ++i){
     for (j = 1; j <= n; ++j){
  if (text[j-1] == pat[i-1]){
      cost[i][j] = mymin(index, cost[i-1][j-1], 
                                 cost[i-1][j]+1, cost[i][j-1]+1);
  }
  else{
      cost[i][j] = mymin(index, cost[i-1][j-1]+1, 
                                 cost[i-1][j]+1, cost[i][j-1]+1);
  }
  dirt[i-1][j-1] = index;  // 方向，方法可参看CLRS中解LCS的方法
     }
 }

 for (j = 0; j <= n; j++){
     if (min_cost > cost[m][j]){
  min_n = j;
  min_cost = cost[m][j];
     }
 }
 print_pat_match(text, dirt, m-1, min_n-1);  // 打印子串
 cout << endl;
 return min_cost;                                // 返回最小差别数
}

int main()
{
 string text("Have a hsssppy day!");   // 文本串
 string pat("happy");                  // 模式
 int diff = approx_match(text, pat);   // 近似串差别数
 cout << "diff = " << diff << endl;
}

空间复杂度仍然可以改进到O(n)，不在赘述。