判定文字列ループ変位

文字列s中の文字が任意の位置を循環移動した後に別の文字列tを得ることができる場合、sはtのループシフトと呼ばれる.例えば、ACTGACGはTGACGACの1つのループシフトであり、逆も同様である.この条件のゲノム配列における研究を判定することは非常に重要である.アルゴリズムを記述して、2つの与えられた文字列sとtが互いにループ変位であるかどうかを検査する.
これは私が『アルゴリズム(第4版)』で見た練習問題で、当時の第一の考えは文字列tを遍歴し、異なるインデックス位置から文字列tを2つのサブ列に分解し、順序を交換してつなぎ合わせた後、sと等しいかどうかを考えることだった.アルゴリズムは次のとおりです.

 public static boolean isCircularRotation(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int length = s.length();
        for (int i = 1; i <= length; i++) {
            String left = s.substring(0, i);
            String right = s.substring(i, length);
            if ((right + left).equals(t)) {
                return true;
            }
        }
        return false;
    }

その後、答えを見て、1行のコードでできるとヒントを与えました.その時考えて、あまり不可能だと感じて、やめました.今日この本を勉强し直した时、またこの问题を见て、急に思いつきました＾(￣)￣)＾.コードは次のとおりです.

public static boolean isCircularRotation(String s, String t) {
        return s.length() == t.length() && (t + t).contains(s);
    }

解釈:文字列sとtが互いにループ変位している場合、sは「AB」に分解でき、tは「BA」に分解できる.では、tは自身とつながって「BABA」となり、明らかにsが含まれている.この考え方は巧みで、もちろん、アルゴリズムの効率はあまり向上していないと思っています.