LCSと接尾辞配列

この間のLCS問題
LCS問題とその拡張により、複数の文字列のすべての共通サブ列が見つかります。
接尾辞の木の方法を使って、プログラムの珠玉を見た後に接尾辞の木のグループが更に簡潔で効率的だと感じて、だから再び実現します
単一文字列の最も長い繰返しサブ列と最も長いm回のサブ列を見つけます.
 

import java.util.ArrayList;
import java.util.Collections;

/**

 * User: yiminghe
 * Date: 2009-3-2
 * Time: 23:36:32

 */
public class LCS {


    //                  
    private static ArrayList<String> getSuffixArray(String s) {
        ArrayList<String> al = new ArrayList<String>();
        int l = s.length();
        for (int i = 0; i < l; i++) {
            al.add(s.substring(i));
        }


        Collections.sort(al);
        return al;
    }


    /**
     * @param s    
     * @return      m    
     */
    public static String getLongestCommonSubstring(String s, int m) {
        String longStr = "";
        String[] suffixes = getSuffixArray(s).toArray(new String[0]);
        for (int i = 0; i < suffixes.length - (m - 1); i++) {
            int tl = getCommonLength(suffixes, i, i + m - 1);
            if (tl > longStr.length())
                longStr = suffixes[i].substring(0, tl);
        }
        return longStr;


    }

    //  n        
    private static int getCommonLength(String[] s, int start, int end) {
        int c = 0;

        while (true) {
            for (int i = start; i <= end; i++)
                if (s[i].length() <= c) return c;
            for (int i = start; i < end; i++)
                if (s[i].charAt(c) != s[i + 1].charAt(c)) return c;
            ++c;
        }

    }


    public static void main(String[] args) {
        String test = "banana";
        System.out.println(getLongestCommonSubstring(test,3));
    }
}