1題のアルゴリズム|繰り返し重ね合わせ文字列マッチング


タイトル
2つの文字列AとBが与えられ、重複する重複する文字列Aの最小回数が、文字列Bが重複する文字列Aのサブ列となり、存在しない場合は−1を返す

例えば、A=「abcd」、B=「cdabcdab」である.答えは3で、Aが3回繰り返して「abcdabcdabcd」になったため、Bはそのサブ列である.Aは2回繰り返して「abcdabcd」となり、Bはそのサブ列ではない.
に注意
AとB文字列の長さは1と10000区間の範囲内である
問題を解く構想.
まず、終了条件、すなわちAコピーの最大文字列長を見つけます.Aの長さがBの長さより大きい場合、AB文字列を含まない文字列を2回コピーすると、後で含めることはできません.この場合の最大長は2*A.lengthです.Aの長さがBの長さより小さい場合、コピーAの文字列長がA.length+B.lengthである場合、Aの文字列にBの文字列が含まれていなければ、後にも含まれず、このときの最大長はA.length+B.lengthである.両者を組み合わせて最大値A.length*2+B.lengthをとる.
インプリメンテーションコード
public static int repeatedStringMatch(String A, String B) {
    //         
    int max_length = (A.length()*2 + B.length()) < 10000 ? (A.length()*2 + B.length()) : 10000;
    //   A
    StringBuilder sb = new StringBuilder(A);
    //     
    int repeated_count = 1;
    while (sb.length()<= max_length){
        if (sb.lastIndexOf(B) > -1){
            return repeated_count;
        }
        repeated_count++;
        sb.append(A);
    }
    return -1;
}

コードをスキャンして公衆番号(公衆番号を検索します:平頭兄の技術の博文)に注目して一緒に交流して勉強します