https://algospot.com/judge/problem/read/COUNTPALIN#




섬시티(SumCity)에는 도시를 가로지르는 거대한 대로가 있다. 그 대로를 따라 상가들이 늘어서 있다. 석환이는 섬시티의 지도를 보고 상가들의 앞 글자를 쭉 읽으며 회문이 되는 부분 문자열(palindrome)을 찾는 것을 즐긴다. 또한 한 글자는 회문인것이 명백하므로, 석환이는 길이가 2이상인 부분 문자열들에 대해서만 회문의 갯수를 세고 싶다.

예를 들어 1번지부터 존재하는 상가명들이 다음과 같다고 하자:

Engine Studio
White dwarf bucks
Honja
Sumsung
Positronic arts
Sanwang money
Harmplus
Algojaspot
Affle
Hoohle
Down team
Angdroid
Andromeda Express

이 때 첫 글자만 딴다면 'EWHSPSHAAHDAA'이다.
석환이가 원하는 부분문자열은 'HSPSH','SPS','HAAH','AA','AA'으로 답은 5이다.

석환이를 돕기 위해 유능한 해커인 당신은 섬시티 시청을 해킹해서 지도를 빼와 출력한 후 문자 인식을 통해 대로상에 존재하는 모든 상가들의 첫 글자들을 모은 하나의 문자열을 얻는데 성공했다.
이제 당신이 할 유일한 일은 석환이가 원하는 답을 구하는 것이다.

입력

첫 번째 줄에는 입력의 종류 T(<=50)이 주어진다.
그 뒤로 T개의 줄에 하나의 숫자 N(1<=N<=1,000,000)과 길이가 N인 문자열이 주어진다.
문자열은 항상 알파벳 소문자로 구성되어있고, 공백은 없다.

출력

각 입력마다 석환이가 원하는 답을 한 줄씩 출력한다.

예제 입력3 1 a 4 aaaa 8 abcddcba예제 출력0 6 4


시간초과가 계속 나네요...


맨체스터 알고리즘을 활용하라는데 이해가 잘 안가네요


혹시 맨체스터 알고리즘좀 쉽게 설명해줄 분 계신가요 


우선 아래는  작성한 코드... 




import java.util.Scanner;


public class COUNTPALIN {


static Scanner scan = new Scanner(System.in);


public static void main(String[] args) {

   // TODO Auto-generated method stub

   int testCase = scan.nextInt();

   while(testCase > 0)

   {

    countPalin();

       testCase--;

   }

}


private static void countPalin() {

// TODO Auto-generated method stub

int num = scan.nextInt();

String arr = scan.next();

int count = 0;

boolean flag = true;

for(int i=0; i<num; i++)

{

int left = i;

int right = i+1;

flag = true;

int left2 = i+1;

int right2 = i+1;

while(left>=0 && right < arr.length())

{

if(flag && arr.charAt(left) == arr.charAt(right) )

{

count++;

flag = true;

left--;

right++;

}

else

break;

}

while(left2>0 && right2+1 < arr.length())

{

if(left2>0 && arr.charAt(left2-1) == arr.charAt(right2+1))

{

count++;

flag = true;

left2--;

right2++;

}

else

break;

}

}

System.out.println(count);

}

}