5,530
社区成员




if(匹配)
int ia = b[i-1][j-1] + score[i];
else {
//下面这两步如果直接这么下去的话会把最终匹配结果的"跨度"拉的很大
//因为有length
//所以这里得加点条件限制一下
int ib = b[i][j-1] + 0;
int ic = b[i-1][j] + 0;
//表b应该是这样的,横竖无所谓....
//X处的值为2^7 + 2^9 + 2^12
//别处的值还是不写了....
66 430 36 50
33
42
433
24
11
233
423
111
33
643
231
33
543 X
//大致说一下思路,可能不对
//这个应该是动态规划,类似LCS
//定义一个二维数组b,大小为两个字符串长度(一个数算一个长度单位),每个位置对应目前匹配最大分
//如[2,3]表示src的前二个数与sub的前三个数的最大匹配分
//然后初始化二维,各个元素为0;
//然后在定义一个二维数组score,用来记录src里每个数的匹配分,第一个数的匹配分为2,第二为4,第三为8,第四为16依次类推....
//然后看下面....
memset(b,0,sizeof(b)); //先把b里的分都设置为0
for (int i = 1; i <= m; ++i) //DP
for (int j = 1; j <= n; ++j) {
if(匹配)
int ia = b[i-1][j-1] + score[i]; //匹配的情况,得score[i]分
else {
int ib = b[i][j-1] + 0; //不匹配的情况一:得0分
int ic = b[i-1][j] + 0; //不匹配的情况二:得0分
}
b[i][j] = Max(ia,ib,ic); //三种情况得分后,从中选取最大分,记录下来
}
//最后结果在b[m,n],因为src里每个数的匹配分是以2,4,8,16……的规律记录的
//所以可以根据最终结果为多少来判断匹配的数在第几个位置,也就知道sub在src里相似度最高的字串了
//举个例子,如果最后结果为12
//12 = 4 + 8 = 2^2 + 2^3
//所以在src里的数为第2个和第3个