一个字串匹配问题

kenmark

两个字符串的相似度匹配
src:33， 42， 433， 24， 11， 233， 423， 111， 33， 643， 231， 33， 543
sub:66， 430， 36， 50
allowance:15
src：主串
sub：字串
allowance：容差值
隐含变量：lengh 大小为sub长度的1/3
现求一算法，求出sub在src里相似度最高的字串
1：类似于lcs算法，找到最大公共子串，但是这里有个容差值存在。其中最大子串中，66并不被匹配
2：length的意思是最大可以跨越的长度。例如430可以匹配到423， 但是36并不能匹配到111
，那么就可以用到length了往后移动可以发现符合条件的33

double GetSimRate(int src[], int srcSize, int sub[], int subSize, int allowance)
{
double simRate = 0.0;
//请补齐
reutrn simRate;
}
关于这个相似度的计算是这样的
如果跳过一个数字，则相似度相应减去一定数值，利用容差值则不去管它。。
如果某个没有匹配到（字串中），也要减去
转自http://topic.csdn.net/u/20080711 ... 0-f64fd2e22572.html
一个兄弟的问题，大家帮忙看看

无心人

66最佳匹配是643还是634
如果存在636是否优先于643 634

kenmark

66在本例里面没有匹配，因为正文中没有66+-15范围内的值，而且题目要求的只是模式串的子串
此外我对他的匹配评分有点问题，是长度优先还是差值最小优先，我已经问了~
题目似乎有些小瑕疵

mathe

主要是评分函数没有定义清楚。定义清楚了以后，直接穷举应该算一种不错的方法了。但是用动态规划应该可以减少时间复杂度，但是空间复杂度不小。

chaoge

这个问题已经有解决方案。如果你用过beyond compare这样的工具体会到。记得去年找到了一篇这样的文章，一直没时间仔细研究，不是很难，但是有点绕脑子，技巧性比较强。当然罗，已经是成型的理论，不是关公耍大刀。

kenmark

原帖由 mathe 于 2008-7-29 12:42 发表
主要是评分函数没有定义清楚。定义清楚了以后，直接穷举应该算一种不错的方法了。但是用动态规划应该可以减少时间复杂度，但是空间复杂度不小。

嗯，不同的评分函数可能造成动归不正确，搜索加点剪枝可能是通行的办法，实现起来也比较容易

mathe

原帖由 kenmark 于 2008-7-30 08:14 发表

嗯，不同的评分函数可能造成动归不正确，搜索加点剪枝可能是通行的办法，实现起来也比较容易

的确如此.