算法知识梳理(3) - 字符串算法第二部分

算法知识梳理(3) - 字符串算法第二部分
泽毛

2017.11.07 阅读 563 评论 0 喜欢 0

面试算法代码知识梳理系列

算法知识梳理(1) - 排序算法
算法知识梳理(2) - 字符串算法第一部分
算法知识梳理(3) - 字符串算法第二部分


一、概要

本文介绍了有关字符串的算法第二部分的Java代码实现,所有代码均可通过 在线编译器 直接运行,算法目录:

  • 查找字符串中的最长重复子串
  • 求长度为N的字符串的最长回文子串
  • 将字符串中的*移到前部,并且不改变非*的顺序
  • 不开辟用于交换的空间,完成字符串的逆序C++
  • 最短摘要生成
  • 最长公共子序列

二、代码实现

2.1 查找字符串中的最长重复子串

问题描述

给定一个文本文件作为输入,查找其中最长的重复子字符串。例如,"Ask not what your country can do for you, but what you can do for your country"中最长的重复字符串是“can do for you”,第二长的是"your country"

解决思路

这里解决问题的时候用到了 后缀数组 的思想,它指的是字符串所有右子集的集合,例如字符串abcde,它的后缀数组就为["abcde", "bcde", "cde", "de", "e"]

解法分为三步:

  • 求得输入字符串p的后缀数组,把它存放在一个List当中,这里注意去掉空格的情况。
  • List中的所有元素进行快速排序。快速排序的目的不在于使得整个数组有序,而在于 使得前缀差异最小的两个字符串在数组中位于相邻的位置,对于上面的例子,其排序结果为:
后缀数组的快速排序结果
后缀数组的快速排序结果
  • 遍历排序后的数组,只需要对数组中的 相邻的两个元素 从头开始比较,计算出这两个字符串相同前缀的长度。遍历之后,取得的最大值就是最长重复子串的长度,而这两个字符串的相同前缀就是最长重复子串。

实现代码

import java.util.ArrayList;
import java.util.List;
import java.lang.String;

class Untitled {

    static void quickSortStr(List<String> c, int start, int end){
        if(start >= end)
            return;
        int pStart = start;
        int pEnd = end;
        int pMid = start;
        String t = null;
        for (int j = pStart+1; j <= pEnd; j++) {
            if ((c.get(pStart)).compareTo(c.get(j)) > 0) {
                pMid++;
                t = c.get(pMid); 
                c.set(pMid, c.get(j)); 
                c.set(j, t);
            }
        }
        t = c.get(pStart); 
        c.set(pStart, c.get(pMid)); 
        c.set(pMid, t);
        quickSortStr(c, pStart, pMid-1);
        quickSortStr(c, pMid+1, pEnd);
    }
    
    //获得两个字符串从第一个字符开始,相同部分的最大长度。
    static int comLen(String p1, String p2){
        int count = 0;
        int p1Index = 0;
        int p2Index = 0;
        while (p1Index < p1.length()) {
            if (p1.charAt(p1Index++) != p2.charAt(p2Index++))
                return count;
            count++;
        }
        return count;
    }

    static String longComStr(String p, int length){
        List<String> dic = new ArrayList<String>();
        int ml = 0 ;
        for (int i = 0; i < length; i++) {
            if (p.charAt(i) != ' ') {
                //构造所有的后缀数组。
                dic.add(p.substring(i, p.length()));
            }
        }
        String mp = null;
        //对后缀数组进行排序。
        quickSortStr(dic, 0, dic.size()-1);
        //打印排序后的数组用于调试。
        for (int i = 0; i < dic.size(); i++) {
            System.out.println("index=" + i + ",data=" + dic.get(i));
        }
        for (int i = 0; i < dic.size()-1; i++) {
            int tl = comLen(dic.get(i), dic.get(i+1));
            if (tl > ml) {
                ml = tl;
                mp = dic.get(i).substring(0, ml);
            }
        }
        return mp;
    } 

    public static void main(String[] args) {
        String source = "Ask not what your country can do for you, but what you can do for your country";
        System.out.println("result = " + longComStr(source, source.length()));
    }
}

运行结果

>> result = can do for you

2.2 求长度为 N 的字符串的最长回文子串

问题描述

长度为N的字符串,求这个字符串里的最长回文子串,回文字符串 简单来说就是一个字符串正着读和反着读是一样的。

解决思路

这里用到的是Manacher算法,首先需要对原始的字符串进行预处理,即在每个字符之间加上一个标志位,这里用#来表示,这会使得对于任意一个输入,经过处理后的字符串长度为2*len+1,也就是说 处理后的字符串始终为奇数

在上面我们已经介绍过,回文串中最左或最右位置的字符与其对称轴的距离称为 回文半径Manacher定义了一个数组RL[i],它表示 i个字符为对称轴的回文串最右一个字符与字符i的闭区间所包含的字符个数,以google为例,经过处理后的字符串为#g#o#o#g#l#e,那么RL[i]的值为:



RL[i]-1的值就是原始字符串中,以位置 i为对称轴的最长回文串的长度,那么接下来的问题就变成如何计算 RL[i]数组。

首先,我们需要两个辅助的变量maxidRmaxid,它表示当前计算的回文字符串中,所能触及到的最右位置,而maxid则表示该回文串的对称轴所在位置,而RL[maxid]为该回文串的距离。

假设我们此时遍历到了第i个字符,那么这时候有两种情况:

(1) i < maxidR

在这种情况下,我们知道p[maxid+1, .., maxid+RL[maxid]-1]p[maxid-1, .., maxid-RL[maxid]+1]部分是关于p[maxid]对称的,利用这个有效信息,可以避免一些不必要的判断。

现在,我们获得i关于maxid的对称点j,这个点位于maxid的左侧,因此,我们已经计算过以它为中心的回文字符串长度RL[j],对于以p[j]为中心的回文字符串有两种情况:

  • j为中心的回文字符的最左边j-(RL[j]-1) 大于等于 maxidR关于maxid的对称点maxid-(maxidR-maxid),在这种情况下,我们可以推断出以i为对称点的RL[i]的值最小为RL[j]
  • 大于的情况,可以保证以i为对称点的RL[i]至少为(maxidR-i)+1

当然这上面只是推测出的 最小情况,之后仍然要继续遍历来更新RL[i]的值。

(2) i >= maxidR

这时候没有任何的已知信息,我们只能从i的左右两边慢慢遍历。

实现代码

class Untitled {
    
    static int maxSynStr(char ip[], int len) {
        int size = 2*len + 1;
        char a[] = new char[size];
        int RL[] = new int[size];
        int i = 0;
        int n;
        while (i < len) {
            a[(i<<1)+1] = ip[i];
            a[(i<<1)+2] = '#';
            i++;
        }
        a[0] = '#';
        //最远字符的中心对称点。
        int maxid = 0;
        //探索到的最远字符。
        int maxidR = 0;
        int ans = 0;
        RL[0] = 1;
        for (i = 1; i < size; i++) {
            //首先推测出i为中心的最小回文半径。
            int offset = 0;
            if (i < maxidR) {
                //j是关于maxid在左边的对称点。
                int j = maxid-(i-maxid);
                //获取之前计算出的以j为中心的回文半径。
                if (j-(RL[j]-1) >= maxid-(maxidR-maxid)) {
                    offset = RL[j]-1;
                } else {
                    offset = maxidR-maxid;
                } 
            }
            do {
                offset++;
            } while(i-offset >= 0 && i+offset < size && a[i+offset] == a[i-offset]);
            //最后一次是匹配失败的,因此要减去1。
            offset--;
            //RL[i]的值包括了自己,因此要加1。
            RL[i] = offset+1;
            //更新当前最大的回文半径。
            if (i+offset > maxidR){
                maxidR = i+offset;
                maxid = i;
            }
            if (RL[i] > ans) {
                ans = RL[i];
            }
        }
        return ans-1;
    } 
    
    public static void main(String[] args) {
        char[] source = "google".toCharArray();
        System.out.println("result=" + maxSynStr(source, 6));
    }
}

运行结果:

>> result=4

2.3 将字符串中的 * 移到前部,并且不改变非 * 的顺序

问题描述

将字符串中的*移到前部,并且不改变非*的顺序,例如ab**cd**e*12,处理后为*****abcde12

解决思路

我们可以将整个数组分为两个部分:有可能包含*字符的部分和一定不包含*字符的部分。初始时候,整个数组只有有 有可能包含*字符的部分,那么我们就可以 从后往前 遍历,每遇到一个非*的字符就把它放到 一定不包含*字符的部分,由于需要保持非*的顺序,因此需要将它插入到该部分的首部。

实现代码

class Untitled {

    static void moveNullCharPos(char p[], int length) {
        if (length > 1) {
            char t;
            char c;
            int lastCharIndex = length;
            //必须要从后向前扫描。
            for(int j = length-1; j >=0 ;j--) {
                if ((c = p[j]) != '*') {
                    lastCharIndex--;
                    t = p[lastCharIndex]; p[lastCharIndex] = p[j]; p[j] = t;
                }
            }
        }
        System.out.println(p);
    }

    public static void main(String[] args) {
        char[] source = "ab**cd**e*12".toCharArray();
        moveNullCharPos(source, source.length);
    }
}

运行结果:

>> *****abcde12

2.4 不开辟用于交换的空间,完成字符串的逆序(C++)

问题描述

不开辟用于交换的空间,完成字符串的逆序。

解决思路

这里利用的是 两次亦或等于本身 的思想。

实现代码

#include <iostream>
using namespace std;

void reverWithoutTemp(char *p, int length){
    int i = 0;
    int j = length-1;
    while (i < j) {
        p[i] = p[i]^p[j];  
        //实际上是p[i]^p[j]^p[j],这里的p[i]和p[j]指的是原始数组中的值。
        p[j] = p[i]^p[j];  
        //实际上是(p[i]^(p[i]^p[j]^p[j]))^(p[i]^p[j]^p[j]),这里的p[i]和p[j]指的是原始数组中的值。
        p[i] = p[i]^p[j];  
        i++;j--;
    }
    std::cout << p << std::endl;
}

int main() {
    char p[] = "1234566";
    reverWithoutTemp(p, 7);
    return 0;
}

运行结果:

>> 6654321

2.5 最短摘要生成

问题描述

给定一段描述w和一组关键字q,我们从这段描述中找出包含所有关键字的最短字符序列,这个最短字符序列就称为 最短摘要

  • 最短字符序列必须包含所有的关键字
  • 最短字符序列中关键字的顺序可以是随意的

解决思路

假设我们的输入序列如下所示,其中w表示非关键字的字符串,而q则表示关键字的字符串:

w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

这里,我们引入额外的三个变量pStartpEndflag数组,flag数组用于统计pStartpEnd之间关键字的命中情况。

这里说明一下flag数组的作用,flag数组和关键字p数组的长度相同,每命中一个关键字,就将flag数组的对应位置+1,而flagSize只有在每次遇到一个新的关键字时才更新,因此它表示flag数组中 不重复的关键字的个数

算法的步骤如下:

  • 第一步:我们将pEndw[0]开始移动,每发现一个命中的关键字,就更新flag[]数组,直到w[pStart,..,pEnd] 包含了所有的关键字,即w0,w1,w2,w3,q0,w4,w5,q1
  • 第二步:开始移动pStart,这时候pStart,..,pEnd之间的长度将会逐渐变短,在移动的过程中,同时更新flag[]数组,直到pStart,...,pEnd之间 不再包含所有的关键字,这时候就可以求得 目前为止的最短摘要长度,即q0,w4,w5,q1
  • 第三步:重复第一步的操作,移动pEnd使得pStart,...,pEnd重新 包含所有的关键字,再执行第二步的操作来 更新最短摘要长度,直到pEnd遍历到w的最后一个元素。

实现代码

class Untitled {

    static int findKey(String[] p1, String p2) {
        int len = p1.length;
        for(int i = 0; i < len; i++) {
            if(p1[i].equals(p2))
                return i;
        }
        return -1;
    }
    
    //p1为原始数据,p2为所有的关键词。
    static int calMinAbst(String[] p1, String[] p2) {
        int p1Len = p1.length;
        int p2Len = p2.length;
        int r;
        int shortAbs = Integer.MAX_VALUE;
        int tAbs = 0;
        int pBegin = 0;
        int pEnd = 0;
        int absBegin = 0;
        int absEnd = 0;
        int flagSize = 0;
        int flag[] = new int[p2Len];
        //初始化标志位数组。
        for (int i = 0; i < p2Len; i++) {
            flag[i] = 0;
        }
        while (pEnd < p1Len) {
            //只有先找到全部的关键词才退出循环。
            while (flagSize != p2Len && pEnd < p1Len) {
                r = findKey(p2, p1[pEnd++]);
                if (r != -1) {
                    if (flag[r] == 0) {
                        flagSize++;
                    }
                    flag[r]++;
                }
            }
            while (flagSize == p2Len) {
                if ((tAbs = pEnd-pBegin) < shortAbs) {
                    shortAbs = tAbs;
                    absBegin = pBegin;
                    absEnd = pEnd-1;
                }
                r = findKey(p2, p1[pBegin++]);
                if (r != -1) {
                    flag[r]--;
                    if (flag[r] == 0) {
                        flagSize--;
                    }
                }
            }
        }
        for (int i = absBegin; i <= absEnd; i++) {
            System.out.print(p1[i] + ",");
        }
        System.out.println("\n最短摘要长度=" + tAbs);
        return shortAbs;
    }

    public static void main(String[] args) {
        String keyword[] = {"微软", "计算机", "亚洲"};
        String str[] = { 
            "微软","亚洲","研究院","成立","于","1998","年",",","我们","的","使命",
            "是","使","未来","的","计算机","能够","看","、","听","、","学",",",
            "能","用","自然语言","与","人类","进行","交流","。","在","此","基础","上",
            ",","微软","亚洲","研究院","还","将","促进","计算机","在","亚太","地区",
            "的","普及",",","改善","亚太","用户","的","计算","体验","。","”"
        };
        calMinAbst(str, keyword);
    }
}

运行结果

>> 微软,亚洲,研究院,还,将,促进,计算机,
>> 最短摘要长度=7

2.6 最长公共子序列

问题描述

经典的LCS问题,这里主要解释一下最长公共子序列的含义。最长公共子串和最长公共子序列的区别:子串串的一个连续的部分子序列则是 不改变序列的顺序,而从序列中去掉任意的元素 而获得的新序列。

解决思路

经典的LCS问题,原理可以参考这篇被广泛转载的文章 程序员编程艺术第十一章:最长公共子序列问题,这里给出简要介绍一下基本的思想。

LCS基于下面这个定理:

LCS 算法定理
LCS 算法定理

最终目的是构建类似于下面的一个矩阵:
LCS 矩阵
LCS 矩阵
  • 对于矩阵,定义c[i][j]:它表示字符串序列A的前i个字符组成的序列A和字符串序列B的前j个字符组成的序列B之间的最长公共子序列的长度,其中i<=A.len,并且j<=B.len
  • 如果A[i]=B[j],那么AB之间的最长公共子序列的最后一项一定是这个元素,也就是c[i][j] = c[i-1][j-1]+1
  • 如果A[i]!=B[j],则c[i][j]= max(c[i-1][j], c[i][j-1])
  • 初始值为:c[0][j]=c[i][0]=0

代码实现

class Untitled {

    static void LCS(char a[], int aLen, char b[], int bLen){
        int c[][] = new int[bLen+1][aLen+1];
        for (int i = 1; i < bLen+1; i++) {
            for (int j = 1; j < aLen+1; j++) {
                if (a[j-1] == b[i-1]) {
                    c[i][j] = c[i-1][j-1] + 1;
                } else {
                    c[i][j] = (c[i-1][j]>c[i][j-1]) ? c[i-1][j]:c[i][j-1];
                }
            }
        }
        int csl = c[bLen][aLen];
        char p[] = new char[csl+1];
        int i = bLen, j = aLen;
        while (i > 0 && j > 0 && c[i][j] > 0) {
            if (c[i][j] == c[i-1][j]) {
                i--;
            } else if(c[i][j] == c[i][j-1]) {
                j--;
            } else if(c[i][j] > c[i-1][j-1]) {
                p[c[i][j]] = a[j-1];
                i--;j--;
            }
        }
        for (i = 1; i <= csl; i++) {
            System.out.print(p[i]);
        }
    } 

    public static void main(String[] args) {
        char p1[] = "aadaae".toCharArray();
        char p2[] = "adaaf".toCharArray();
        LCS(p1, p1.length, p2, p2.length);
    }
}

运行结果

>> adaa

更多文章,欢迎访问我的 Android 知识梳理系列:

生活 转载请联系作者,并注明出处。

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

春光支付宝

支付宝

春光微信

微信


喜欢  |  0

0条评论