【Java -- 算法】字符串算法（二）

一、前言

本文介绍了有关字符串的算法第二部分的 Java 代码实现，算法实例：

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

所有代码均可通过 菜鸟工具在线编译器 直接运行，因此打算整理一下分享给大家。

二、代码 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 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  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