ASM_DP.rar

// 三个int中的最小值 int min(int a, int b, int c) { int arr[3] = { a,b,c }; int min = arr[0]; for (int i = 0; i < 3; i++) if (arr[i] < min) min = arr[i]; return min; } // 基于动态规划的近似串匹配算法 int ASM_DP(char P[], char T[], int m, int n, int K) { int i, j; int** D = new int* [m+1]; for (int u = 0; u < m+1; u++) D[u] = new int[n+1]; for (i = 0; i <= m; i++) for (j = 0; j <= n; j++) D[i][j] = i; for (j = 1; j <= n; j++) { for (i = 1; i <= m; i++) { if (P[i-1] == T[j-1]) D[i][j] = min( D[i - 1][j - 1],D[i - 1][j] + 1,D[i][j - 1] + 1 ); else D[i][j] = min( D[i - 1][j - 1] + 1,D[i - 1][j] + 1,D[i][j - 1] + 1 ); if (D[m][j] <= K) return j; } } }