ブルーブリッジカップ-Tricky and Clever Password(java)

                         Tricky and Clever Password  
                        ：2.0s       ：256.0MB

                
            　　      ，        ——   Copa——                。     ，      。  ，        ，       。  ，                    。

            　　Copa       ，              。            ，              ：        X ，   X     0 ，  2X        。         3  ，     X       ，     X       ，        。            prefix, suffix, middle 。  ， middle          0    ，  prefix 、 suffix      。          A + prefix + B + middle + C + suffix ，   A 、 B 、 C      Copa       ，       ， +        。

            　　      。Copa                    。  ，Copa     、A、B、C    。  ，            ，              Copa   、     。
                
            　　                   ，    1   10^5   。
                
            　　          k ，             3              。   k in {1, 3} 。    k  ，   2           x_i l_i ，              。      x_i   。

            　　     x_i     1             。 l_i       ，              。 middle         。

            　　       ，      。  ：           l_i    ，    k 。
                
            abacaba
                
            1
            1 7
                
            axbya
                
            3
            1 1
            2 1
            5 1
                
            xabyczba
                
            3
            2 2
            4 1
            7 2
                   
            　　   10%    ： n <= 10

            　　   30%    ： n <= 100

            　　   100%    ： n <= 100000

            　　   20%    ，         1 。

package com.sihai.advance;

import java.util.ArrayList;
import java.util.Scanner;

public class Main{

    public int[] getMaxReverse(char[] arrayA, int i, int j) {
        int[] result = new int[2];
        int max = 1;
        int begin = i+1;    //          ，      i   
        int zero = i;      //  i    
        for(i = i + 1;i < j;i++) {
            int start = i - 1;
            int end = i + 1;
            int count = 1;
            while(start >= zero && end <= j) {    //      ，         
                if(arrayA[start] == arrayA[end]) {
                    start--;
                    end++;
                    count = count + 2;
                }
                else
                    break;
            }
            if(count > max) {
                max = count;
                begin = i - (count-1)/2 + 1;
            }
        }
        result[0] = begin;   //         
        result[1] = max;     //       

        return result;
    }

    //  KMP    ，  next   
    public int[] getNext(char[] arrayB) {
        int[] next = new int[arrayB.length + 1];
        int j = 0;
        for(int i = 1;i < arrayB.length;i++) {
            while(j > 0 && arrayB[i] != arrayB[j]) j = next[j];
            if(arrayB[i] == arrayB[j]) j++;
            next[i+1] = j;
        }
        return next;
    }
    //  KMP  ，      arrayB， arrayA           
    public int getKmpFirstPosition(char[] arrayA, char[] arrayB) {
        int position = -1;
        int j = 0;
        int[] next = getNext(arrayB);
        for(int i = 0;i < arrayA.length;i++) {
            while(j > 0 && arrayA[i] != arrayB[j]) j = next[j];
            if(arrayA[i] == arrayB[j])
                j++;
            if(j == arrayB.length) {
                position = i - j + 1;
                break;
            }
        }
        return position;
    }

    public void printResult(String A) {
        //     X = 0 ，      1，     A              ，       
        char[] arrayA = A.toCharArray();
        int[] result0 = getMaxReverse(arrayA, 0, arrayA.length-1);
        int maxLen0 = result0[1];   //            
        // X ！= 0 ，                  ，  suffix   
        int j = arrayA.length - 1;
        int maxLen = 0;     //        ，    0
        int position1 = 0;
        int position2 = 0;
        int position3 = 0;
        int len1 = 0;
        int len2 = 0;
         for(int lenS = 1;lenS < arrayA.length/2;lenS++) {
            char[] tempS = new char[lenS];
            for(int a = 0;a < lenS;a++) 
                tempS[a] = arrayA[j-a];
            if(getKmpFirstPosition(arrayA, tempS) == -1) {
                continue;
            } 
            int tempPosition1 = getKmpFirstPosition(arrayA, tempS) + 1;
            int endPosition1 = tempPosition1+lenS;
            int startPosition3 = arrayA.length-lenS;

            if(startPosition3 <= endPosition1)
                continue;

            int[] result = getMaxReverse(arrayA,tempPosition1+lenS-1,j-lenS);
            int tempLen2 = result[1];
            int tempPosition2 = result[0];

            if(lenS * 2 + tempLen2 > maxLen) {
                position1 = tempPosition1;
                position2 = tempPosition2;
                position3 = j - lenS + 2;
                len1 = lenS;
                len2 = tempLen2;
                maxLen = lenS * 2 + tempLen2;
            }
        }
         if(maxLen0 >= maxLen) {  
             System.out.println("1");
              System.out.println(result0[0]+" "+result0[1]);
         } else {
             System.out.println("3");
             System.out.println(position1+" "+len1);
             System.out.println(position2+" "+len2);
             System.out.println(position3+" "+len1);
         }
    }

    public static void main(String[] args){
        Main test = new Main(); 
        Scanner in = new Scanner(System.in);
    //    System.out.println("        ：");
        String A = in.nextLine();
        test.printResult(A);
    }
}

実行結果:
文字列を入力してください:asdfsfaaaa 1 7 5
$(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('
').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); });