三、例
P508 例11.11
四、练习
在“The BM agorithm is an algorism wt to left” 中寻找algorithm的2-difference匹配，并说 明理由
Example 11.9
P505
二、解决方案----动态规划
1、采用从右向左 右向左的比较方案。 右向左 2、子问题图中 (i,j)表示模板p1,…,pi在以tj为结尾 的正文T中的minimum-difference match.
Difference Table
D[i][j]= the minimum number of difference between p1,…,pi and a segment of T ending at tj.
D[i][j]之间的关系
matchCost = D[i-1][j-1] if pi=tj revisedCost = D[i-1][j-1] +1 if pi≠tj insertCost = D[i-1][j]+1 在tj后面插入pi deleteCost = D[i][j-1] +1 删除tj if pi=tj D[i][j]= D[i-1][j-1] Otherwise, D[i][j]= min(D[i-1][j-1] +1, D[i-1][j]+1, D[i][j-1]+1 )
应用背景 1、字处理程序中的拼写检查 2、语音或文字识别 3、去传输噪声
一、问题与思路
“Difference”
The differences can be any of the following three types. The name of the difference is the operation needed on T to bring it closer to P. revise: The corresponding characters in P and T are different. delete: T contains a character that is missing from P insert: T is missing a character that appear in P.