编程介的小学生 2017-08-29 12:30 采纳率: 20.5%
浏览 765
已采纳

DICS

Problem Description
I think all of you must be skilled in the classic problem Levenshtein Distance , which is more commonly known as Edit Distance. For more historic knowledge and basic concepts, see http://en.wikipedia.org/wiki/Levenshtein_distance .
This time, we are involved in a more complicated one: given two strings SOURCE and DESTINATION , we have 4 operations
Delete: remove the ith character.
Insert: in pos i(the ith character in the first string),you can insert a character, any one as you like.
Change: in pos i,you can change that original character to any other character(of course you won't change it to itself).
Suffix change: which means you can change all characters to an identical character, from the ith pos to the end. For instance: abcdefg, you can make this operation in character b,maybe you can use d and the result is adddddd, or if you use e the result is aeeeeee or if you use this operation in character c with character f,the result is abfffff.
With the help of Suffix change, sometimes the edit distance can be greatly shortened. See the following example

abcdefg
ccccccg

You can first replace every character from the beginning to the end with c,and the first string will be ccccccc,then change the last character c to g. In such way,we can see the edit distance is 2.

Input
Input consists of several test cases, each case contains two line,the first line will show you the SOURCE string, the second line provide the DESTINATION string. You should write a program to caculate the minimum number of operations(delete, insert, changes, suffix change as I mentioned before) of transforming the SOURCE to DESTINATION. You can assume none of string in any case will be longer than "500". Input ends with a line consists of a '#'.
PAY ATTENTION:Both strings consist of either lower or upper letters,in other word in each position there is 52 possibilities.There will be at most 15 test cases.

Output
One line for each case,the edit distance. Output nothing for the "#".

Sample Input
abcdefg
aaaaaaa
#

Sample Output
1

  • 写回答

1条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥85 maple软件,solve求反函数,出现rootof怎么办?
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题