字符串比较问题
一、问题描述
对于长度相同的2 个字符串A和B，其距离定义为相应位置字符距离之和。2 个非空格 字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0；空格与其它字符的距 离为一定值k。 在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干 空格字符所产生的字符串。在字符串A 和B 的所有长度相同的扩展中，有一对距离最小的 扩展，该距离称为字符串A和B的扩展距离。 对于给定的字符串A和B，试设计一个算法，计算其扩展距离。
二、算法设计
这个算法就是要实现一个最优匹配问题，比如字符串A,和字符串B，先是求最优匹配G[1,1],前面一个一是表示到字符串A的和字符串B的第一个位置时，是最优匹配，再求min(G[1，2])，min(G[1,3]).....直到求到min(G[length(A),length(B)])为止。
用G[i][j]记录字符串Ai和Bj的扩展距离。其中Ai={a1,a2…ai}；Bj={b1,b2…bj}。
当i＝0且j＝0时，显然两个空串的扩展距离为0。
字符串长度比较当i＝0且j ≠0时，求两个字符串的扩展距离等价于求字符串Bj与长度为j的仅由空格构成的字符串(空串的长度为j的扩展）的距离，其距离为j′×k(j′为字符串Bj中非空格字符的数量)。
当i≠0且j＝0时,同理可得其扩展距离为i′×k(i′为字符串Ai中非空格字符的数量)。
G[i,j]为字符串A子串a1,a2,a3……ai与字符串B的子串，b1,b2,b3……bj的距离，也就是扩展串<a1,a2,a3……ai>与扩展串<b1,b2,b3……bj>的最佳匹配距离。
其中:
G[i,j]=min{G[i-1,j]+k,G[i,j-1]+k,G[i-1,j-1]+abs(A[i]-B[j]
三、算法描述
初始化过程
G[0][0] = 0;
        i=1 to i=A.length()  G[i][0] = K+G[i-1][0];
        j=1 to j=B.length()  G[0][j] = K+G[0][j-1];
依次计算字符串A,B的最优匹配直到算出min(G[i,j])
        i=1 to i=A.length()           
j=1 to j=B.length()
                G[i][j] = K+G[i-1][j];
                Gouble temp = G[i][j-1]+K;
                if G[i][j]>temp  G[i][j] = temp;
                temp = G[i-1][j-1]+ abs(A(i-1)-B(j-1));
                if G[i][j]>temp  G[i][j] = temp;
输出最优匹配结果
G[length(A),length(B)]
四、算法分析
G[0][0]
G[0][1]
G[0][2]
………
G[0][len(A)]
G[1][0]
G[1][1]
G[1][2]
………
G[1][len(A)]
G[2][0]
G[2][1]
G[2][2]
………
G[2][len(A)]
G[3][0]
G[3][1]
G[3][2]
………
G[3][len(A)]
………
………
………
………
………
G[len(B)][0]
G[len(B)][1]
G[len(B)][2]
………
G[len(B)][len(A)]
以上算法的时间复杂度与空间复杂度均为O(length(A)length(B))。
通过观察以上计算过程，不难发现，在计算G[i][j]时只涉及到G[i-1][j-1],G[i-1][j]与G[i][j-1]。即只用到数组的第i-1行与第i行。
因此在算法中， 若按照从上到下，从左到右的逐行计算过程，只需用两个一维数组保存当前
行与上一行的数据即可，从而可将空间复杂度降为O(n)，进一步若考虑取min(i,j)为列数，则空间复杂度可减至O(min{i,j})。
五、算法实现
import java.io.*;
public class Testsuanfa {
    String A;
    String B;
    Gouble K;
    Gouble[][] G = new Gouble[100][100];
    public String getStr(String a){
        String value = null;
        if(a.equals("A")){
            System.out.print("请输入字符串A：");
        }else if(a.equals("B")){
            System.out.print("请输入字符串B：");
        }
        BuffereGReaGer bfr=new BuffereGReaGer(new
InputStreamReaGer(System.in));
            try {
                value = aGLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
        return value;
    }
    public int getK(){
        int Gvalue = 0;
        String value;
        System.out.print("请输入常量K：");
        BuffereGReaGer bfr=new BuffereGReaGer(new
InputStreamReaGer(System.in));
            try {
                value = aGLine();
                Gvalue = Integer.parseInt(value);
            } catch (IOException e) {
                e.printStackTrace();
            }
        return Gvalue;
    }
    public voiG test(){
        A = Str("A");
        B = Str("B");
        K = K();
        G[0][0] = 0;
        for(int i=1;i<=A.length();i++){
            G[i][0] = K+G[i-1][0];
        }
        for(int j=1;j<=B.length();j++){
            G[0][j] = K+G[0][j-1];
        }
        for(int i=1;i<=A.length();i++){
            for(int j=1;j<=B.length();j++){
                G[i][j] = K+G[i-1][j];
                Gouble temp = G[i][j-1]+K;
                if(G[i][j]>temp){
                    G[i][j] = temp;
                }
                temp = G[i-1][j-1]+Math.abs(A.charAt(i-1)-B.charAt(j-1));
                if(G[i][j]>temp){
                    G[i][j] = temp;
                }
            }
        }
System.out.println("字符串A和B的最小扩展距离为："+G[A.length()][B.length()]);
    }
    public static voiG main(String[] args) {
        Testsuanfa tsf = new Testsuanfa();
        st();}}
六、使用说明
1.输入的第1 行是字符串A；第2 行是字符串B。第3行是空格 与其它字符的距离定值k。
2.将计算出的字符串A和B的扩展距离输出。
3．输入样例
cmc
snmn
2
4.输出结果
10
七、测试结果

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。