最長公共子串|阿里2015筆記試験付加問題2

テーマ:queryとtextが与えられ、小文字で構成されています.同じ順序でqueryに連続して現れる最長連続アルファベットシーケンスの長さをtextで見つけることが要求される.たとえば、queryが「acbac」、textが「acaccbabb」の場合、textの「cba」はqueryに連続して現れる最も長いアルファベットシーケンスであるため、返される結果はその長さ3であるべきである.プログラムの効率に注意してください.
【考え方】
     a    c    b    a    c
a   1    0    0    1    0   
c   0    2    0    0    2
a   1    0    0    1    0
c   0    2    0    0    2
c   0    1    0    0    1
b   0    0    2    0    0
a   1    0    0    3    0    
b   0    0    1    0    0
b   0    0    1    0    0
上記の図に示すように、queryの場合、2次元配列arrで共通シーケンスの長さを記録することができる.charAt(j) = text.charAt(i)ではarr[i][j]=arr[i-1][j-1]+1となり、最大長maxLenを記録してmaxLenに戻る.これは一つの考え方であり,またqueryが発見されると,ここでは1次元配列arrで最大長を記録できることが分かった.charAt(j) = text.charAt(i)、arr[i]=arr[i-1]+1(i=1またはj=1の場合、arr[i]=1).そうでない場合、arr[i]=0:

public class QueryLen {
    public int findMaxLen(String query, String text) {
        int maxLen = 0;
        int[] arr = new int[text.length()];
        for (int i = 0; i < query.length(); i++)
            for (int j = text.length() - 1; j >= 0; j--) {  //       ，  ，                    
                if (query.charAt(i) == text.charAt(j))
                    if (i == 0 || j == 0) arr[j] = 1;
                    else arr[j] = arr[j - 1] + 1;
                else arr[j] = 0;
                maxLen = Math.max(maxLen, arr[j]);
            }
        return maxLen;
    }
    public static void main(String[] args) {
        int len = new QueryLen().findMaxLen("acbac", "acaccbabb");
        System.out.println(len);
        len = new QueryLen().findMaxLen("aabbaabbccddddccbb","fabbaexf");
        System.out.println(len);
    }
}

結果:

3
4