ブルーブリッジカップ-Tricky and Clever Password(java)
11672 ワード
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); }); });