首页 > ACM题库 > HDU-杭电 > hdu 3540 EditingOperation待解决[解题报告]C++
2014
11-05

hdu 3540 EditingOperation待解决[解题报告]C++

EditingOperation

问题描述 :

There are two strings: A and B. We define an editing operation as “Insert a character”, “Delete a character” or “Replace a character”.
So your task is to calculate how many editing operations do we need to make B become the substring of A? If the answer is more than the given limitation, just output -1.

输入:

Multiple test cases.
There are 3 lines in each test case:
String A is given in the first line, and the length of A is from 0 to 1000000.
String B is given in the second line, and the length of B is from 0 to 1000.
In the third line, there is an integer LIM. (0<= LIM <=30)

输出:

Multiple test cases.
There are 3 lines in each test case:
String A is given in the first line, and the length of A is from 0 to 1000000.
String B is given in the second line, and the length of B is from 0 to 1000.
In the third line, there is an integer LIM. (0<= LIM <=30)

样例输入:

annealing
annual
3

样例输出:

1


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  4. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept