2 shunfurh shunfurh 于 2017.08.29 20:30 提问

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个回答

caozhy
caozhy   Ds   Rxr 2017.09.13 23:52
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
廖雪峰python教程阅读之使用disc和set
dictPython内置了字典:dict的支持,dict全称dictionary,在其他语言中也称为map,使用键-值(key-value)存储,具有极快的查找速度。 举个例子,假设要根据同学的名字查找对应的成绩,如果用list实现,需要两个list: names = [‘Michael’, ‘Bob’, ‘Tracy’] scores = [95, 75, 85] 给定一个名字,要查找对应
HDU 3831 DICS
题意: 通过题中给出的4种操作  用最少的次数  从a串变换到b串 思路: 由于操作只有这4种  所以我们可以确定从头到位去匹配a和b一定是正确的 那么状态数一共有多少呢  一共有length[a]*length[b]*(1+num(a~z)+num(A~Z))  状态不多  可以用dp解决 上述计算状态可以表示为dp[i][j][k]  即a串匹配到i同时b串匹配到j  k表示修改后缀
HDU 3831 DICS 递推dp
题意: 给定2个字符串,对上面的字符串进行修改使得其变成下面的字符串 有4种操作: 1、删除一个字符 2、插入一个字符 3、修改一个字符 4、把任意位置开始 [i, strlen] 修改为相同的字符 问最少需要几次操作 #include #include #include #include #include #include #include #include #include #
一个简单的扑克牌小游戏
这是我在慕课学习Java的一个小游戏作业 游戏规则如下: 一、创建一副扑克牌  包括四种花色: 黑桃、红桃、梅花、方片  十三种点数:2——10,J、Q、K、A,不考虑大小王  二、创建两名玩家  玩家有ID、姓名、手牌等属性,手牌为扑克牌的集合 三、洗牌 将之前创建的“一副扑克牌”打乱顺序 四、发牌 将洗牌之后的扑克牌集合,从第一张开始,发给两名玩家,按照一人一张的方式,每人
learn python the hard way---ex50,ex51
windows 以下代码不一定能运行,直接建文件即可$ cd projects $ mkdir gothonweb $ cd gothonweb $ mkdir bin gothonweb tests docs templates $ touch gothonweb/__init__.py $ touch tests/__init__.py
python3 字典遍历操作
python字典遍历
discuz论坛用户密码加密原理
一般我们的加密都是采用md5加密方式:md5(变量)。但是昨天需要整合discuz的论坛,看   他的加密方式也像是md5,但是简单的123加密后竟然解密不出来。后来在网上查了一下,   发现他不只是简单的md5加密,而是“md5+随机”。当然这样更安全了。     网站安全了,程序自然也就复杂了...     discuz的加密方式:md5(md5($password).$salt)
iOS NSPredicate数组筛选
NSPredicate条件查询NSPredicate的作用 简述:Cocoa框架中的NSPredicate用于查询,原理和用法都类似于SQL中的where,作用相当于数据库的过滤取。 **条件查询一般是运用于按照条件要求将数组中符合条件的数据筛选出来形成一个新的数组,主要的功能大概如下:代码,例如:NSMutableArray *preditArray = [NSMutableArray arr
脑电溯源定位
头皮记录的脑电是大脑中很多源在记录点叠加起来的结果,而且,这些源的方向(一般随着皮层的褶皱而变化)对最后测量出来的头皮脑电有很大影响。所以不能简单的把头皮对应的激活位置映射到皮层上去,那就只有借助于溯源方法了。         所谓脑电溯源定位,也即脑电逆向问题,概括的说就是:根据头表测量电位信号,反演估计脑内神经活动源的位置、方向和强度信息。fMRI在空间分辨率上有着EEG不可比拟的优势,那么
单片机控制RS485测控模块
RS485测控模块,非常实用。#include <reg51.h> #define uint unsigned int #define uchar unsigned char #define Tim 65536-50000 sbit DAT0 =P2^2; sbit DAT1 =P2^3; sbit DICS =P2^4; sbit DOCS =P2^5; sbit CLK =P2^6; sbit ADCS =P1^5; sbit DAT3 =P1^6; sbit DAT4 =P1^7; sbit DACS =P3^5; sbit DAT2 =P3^4; bit KeyOn; uchar disp[6]; uint para[8],ptr; uchar ts; uchar DO[3],DI[3],DA[4]; uint AD[16]; void time(uint t) { uint i; for(i=0;i<t;i++); } void write8(uchar x) { uchar i; CLK=1; for(i=0;i<8;i++) { x=x<<1; DAT0=CY; CLK=0; CLK=0; CLK=0; CLK=1; CLK=1; CLK=1; } } void DO24() { write8(DO[2]); write8(DO[1]); write8(DO[0]); DOCS=1; DOCS=0; } uchar read8() { uchar x=0,i; DAT1=1; CLK=1; for(i=0;i<8;i++) { CLK=0;CLK=0;CLK=0; x=x<<1; if(DAT1) x++; CLK=1;CLK=1;CLK=1; } return x; } void DI24() { DICS=0; DICS=1; DI[2]=read8(); DI[1]=read8(); DI[0]=read8(); } void TLC5620(uchar ch,uchar x) { uchar i,p; //p=ch<<6; CLK=0; p=(ch*2+1)<<5; for (i=0; i<3; i++) { p=p<<1; DAT2=CY; CLK=1; CLK=0; } p=x; for (i=0; i<8; i++) { p=p<<1; DAT2=CY; CLK=1; CLK=0; } DACS=0; DACS=1; CLK=1; } uint TLC1543(uchar p) { uint res=0; uchar i; CLK=0; ADCS=0; p=p<<4; for (i=0;i<10;i++) //把通道号打入1543 { p=p<<1; DAT4=CY; CLK=1; CLK=0; } ADCS=1; //等待AD转换 time(50); ADCS=0; for (i=0;i<10;i++) //取D9--D5 { CLK=1; res<<=1; DAT3=1; if(DAT3) res++; CLK=0; } ADCS=1; CLK=1; return res; } void tim0() interrupt 1 //定时中断 { static uchar i,j; TH0=Tim>>8;TL0=Tim&0xff; DI24(); DO24(); if(++i>3) i=0; if(++j>15) j=0; TLC5620(i,DA[i]); AD[j]=TLC1543(j); if(ts<255) ts++; }