Manacher의 알고리즘 (선형 시간에서 가장 긴 회문 부분 문자열을 찾는 알고리즘)
Manacher의 알고리즘을 소화하기 위해 약 6 ~ 8 시간을 소비 한 후 수건을 던질 준비가되었습니다. 하지만 제가하기 전에 어둠 속에서 마지막 한 장이 있습니다. 누구든지 설명 할 수 있습니까? 코드는 신경 쓰지 않습니다. 누군가가 알고리즘 을 설명해주기를 바랍니다 .
다음은 다른 사람들이 알고리즘을 설명 할 때 좋아하는 곳인 것 같습니다. http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
나는 당신이 왜 'abba'를 # a # b # b # a #으로 바꾸고 싶어하는지 이해합니다. 예를 들어, 앞서 언급 한 웹 사이트의 작성자는 알고리즘의 핵심 부분이 다음과 같다고 말합니다.
if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥ P[ i' ]. (Which we have to expand past
the right edge (R) to find P[ i ])
P [i '] = 7이고 P [i]가 R-i보다 작거나 같지 않을 때 P [i]가 5와 같다고 한 지점에서 말했기 때문에 이것은 잘못된 것 같습니다.
알고리즘에 익숙하지 않은 경우 다음 링크가 더 있습니다. http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (나는 이것을 시도했지만 용어가 끔찍하고 혼란 스럽습니다. 첫째, 정의되지 않은 사항이 있습니다. 또한 변수가 너무 많습니다. 어떤 변수가 무엇을 참조하는지 기억하기 위해 체크리스트가 필요합니다.)
또 하나는 http://www.akalin.cx/longest-palindrome-linear-time (행운을 빕니다)
알고리즘의 기본 요점은 선형 시간에서 가장 긴 회문을 찾는 것입니다. 최소한의 노력으로 O (n ^ 2)에서 할 수 있습니다. 이 알고리즘은 O (n)으로 내려 가기 위해 꽤 "영리"해야합니다.
링크 설명에서 논리가 옳지 않다는 데 동의합니다. 아래에 몇 가지 세부 정보를 제공합니다.
Manacher의 알고리즘은 i를 중심으로 한 회문이 얼마나 확장되는지를 포함하는 테이블 P [i]를 채 웁니다. P [5] = 3이면 위치 5의 양쪽에있는 3 개의 문자가 회 문의 일부입니다. 이 알고리즘은 긴 회문을 찾았다면 회 문의 오른쪽에있는 P 값을 왼쪽에있는 P 값을보고 빠르게 채울 수 있다는 사실을 활용합니다. 같은.
말씀하신 사례를 설명하는 것으로 시작한 다음 필요에 따라이 답변을 확장하겠습니다.
R은 C를 중심으로하는 회 문의 오른쪽 인덱스를 나타냅니다. 표시 한 위치의 상태는 다음과 같습니다.
C=11
R=20
i=15
i'=7
P[i']=7
R-i=5
논리는 다음과 같습니다.
if P[i']<=R-i: // not true
else: // P[i] is at least 5, but may be greater
링크의 의사 코드는 테스트가 실패하면 P [i]가 P [i ']보다 크거나 같아야하지만 Ri보다 크거나 같아야한다고 생각하고 설명이이를 뒷받침합니다.
P [i ']가 Ri보다 크기 때문에 i'를 중심으로하는 회문은 C를 중심으로 한 회문을지나 확장됩니다. i를 중심으로하는 회문은 적어도 Ri 문자의 너비가 될 것입니다. 하지만 우리는 그 이상을 명시 적으로 검색해야합니다.
P [i ']가 Ri보다 크지 않다면 i'를 중심으로하는 가장 큰 회문은 C를 중심으로하는 가장 큰 회문 내에 있으므로 P [i]가 P [i보다 클 수 없음을 알았을 것입니다. ']. 그렇다면 우리는 모순이 될 것입니다. 그것은 우리가 i에 중심을 둔 회문을 P [i ']를 넘어 확장 할 수 있다는 것을 의미하지만, 가능하다면 대칭으로 인해 i'를 중심으로 회문을 확장 할 수있을 것입니다. 가능한 한 커야합니다.
이 경우는 이전에 설명되어 있습니다.
C=11
R=20
i=13
i'=9
P[i']=1
R-i=7
이 경우 P [i '] <= Ri입니다. 우리는 여전히 C를 중심으로 한 회 문의 가장자리에서 7 자 떨어져 있기 때문에 i 주변의 최소 7자가 i '주변의 7 자와 동일하다는 것을 알고 있습니다. i '주위에는 한 문자 회문 만 있었으므로 i 주위에도 한 문자 회문이 있습니다.
j_random_hacker는 로직이 다음과 비슷해야한다는 것을 알아 차 렸습니다.
if P[i']<R-i then
P[i]=P[i']
else if P[i']>R-i then
P[i]=R-i
else P[i]=R-i + expansion
P [i '] <Ri이면 P [i] == P [i']를 알 수 있습니다. 아직 C를 중심으로 한 회문 안에 있기 때문입니다.
P [i ']> Ri이면 P [i] == Ri를 알 수 있습니다. 그렇지 않으면 C를 중심으로하는 회문이 R을지나 확장되었을 것입니다.
따라서 확장은 P [i '] == Ri 인 특수한 경우에만 실제로 필요하므로 P [i]의 회문이 더 길 수 있는지 알 수 없습니다.
이는 실제 코드에서 P [i] = min (P [i '], Ri)를 설정 한 다음 항상 확장하여 처리됩니다. 확장이 필요하지 않은 경우 확장에 걸리는 시간이 일정하기 때문에 이러한 방식으로 시간 복잡성이 증가하지 않습니다.
이 사이트의 알고리즘은 특정 시점에서 이해할 수있는 것 같습니다. http://www.akalin.cx/longest-palindrome-linear-time
이 특정 접근 방식을 이해하려면 종이에 문제를 해결하고 가능한 각 센터의 회문을 확인하지 않도록 구현할 수있는 트릭을 파악하는 것이 가장 좋습니다.
먼저 자신에게 답하십시오. 주어진 길이의 회문을 찾았을 때 5라고 가정 해 보겠습니다. 다음 단계로 회문 끝으로 건너 뛸 수 없습니까 (4 글자와 4 개 중간 글자 건너 뛰기)?
길이가 8 인 회문을 만들고 길이가 8보다 큰 또 다른 회문을 배치하려고하면, 그 중심이 첫 번째 회 문의 오른쪽에있는 것이 우스운 것을 발견 할 것입니다. 시도해보십시오 : 길이가 8 인 회문-WOWILIKEEKIL-Like + ekiL = 8 이제 대부분의 경우 두 E 사이의 위치를 중심으로, 숫자 8 사이의 위치를 길이로 적고 마지막 L을 찾아서 점프 할 수 있습니다. 더 큰 회 문의 중심.
이 접근 방식은 올바르지 않습니다. 더 큰 회 문의 중심이 ekiL 안에있을 수 있으며 마지막 L 이후 점프하면 놓칠 수 있습니다.
LIKE + EKIL을 찾은 후이 알고리즘이 사용하는 배열에 8을 배치하면 다음과 같습니다.
[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]
...에 대한
[#, W, #, O, #, W, #, I, #, L, #, I, #, K, #, E, #]
트릭은 8 이후의 다음 7 (8-1) 숫자가 왼쪽과 동일 할 것이라는 것을 이미 알고 있으므로 다음 단계는 8의 왼쪽에서 8의 오른쪽으로 7 개의 숫자를 자동으로 복사하는 것입니다. 그들은 아직 최종적이지 않다는 것을 염두에 두십시오. 배열은 다음과 같습니다.
[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] ( 우리는 8에 있습니다)
...에 대한
[#, W, #, O, #, W, #, I, #, L, #, I, #, K, #, E, #, E, #, K, #, I, #, L]
그러한 점프가 현재 솔루션을 파괴하고 우리가 알아 차릴 수있는 것을 확인하는 예를 만들어 보겠습니다.
WOWILIKEEKIL-EKIL 내 어딘가에 중심이있는 더 큰 회문을 만들어 보겠습니다. 그러나 그것은 불가능합니다. 우리는 EKIL이라는 단어를 회문을 포함하는 것으로 바꾸어야합니다. 뭐? OOOOOh-그게 트릭입니다. 현재 회 문의 오른쪽에 중심이있는 더 큰 회문을 가질 수있는 유일한 가능성은 회 문의 오른쪽 (왼쪽)에 이미 있다는 것입니다.
WOWILIKEEKIL을 기반으로 하나를 구축해 보겠습니다. 예를 들어 I를 더 큰 회 문의 중심으로 사용하여 EKIL을 EKIK로 변경해야합니다. LIKE도 KIKE로 변경해야합니다. 까다로운 회 문의 첫 글자는 다음과 같습니다.
WOWIKIKEEKIK
이전에 말했듯이-마지막으로 KIKEEKIK보다 더 큰 팔린 드롬의 중심이되게하십시오.
WOWIKIKEEKIKEEKIKIW
배열을 우리의 오래된 팔린 드롬까지 만들고 추가 정보를 어떻게 활용하는지 알아 봅시다.
...에 대한
[_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W]
[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8
우리는 다음 I-세 번째가 가장 긴 팔린 드롬이 될 것이라는 것을 알고 있습니다.하지만 잠시 잊어 버리겠습니다. 배열의 숫자를 8의 왼쪽에서 오른쪽 (8 개의 숫자)으로 복사합니다.
[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]
루프에서 우리는 숫자 8과 E 사이에 있습니다. K (현재 가장 큰 팔린 드롬의 마지막 문자)로 바로 이동할 수없는 I (가장 큰 팔린 드롬의 미래 중간)의 특별한 점은 무엇입니까? 특별한 점은 어레이의 현재 크기를 초과한다는 것입니다. 어떻게? 3의 오른쪽으로 3 칸 이동하면 배열을 벗어난 것입니다. 그것은 그것이 가장 큰 팔린 드롬의 중앙 일 수 있고 당신이 점프 할 수있는 가장 먼 것은이 문자 I라는 것을 의미합니다.
이 답변의 길이에 대해 죄송합니다-알고리즘을 설명하고 싶었고 확신 할 수 있습니다-@OmnipotentEntity가 옳았습니다-설명 한 후 더 잘 이해합니다 :)
지금까지 다음 링크에서 가장 좋은 설명 중 하나를 찾았습니다.
http://tarokuriyama.com/projects/palindrome2.php
또한 질문에 언급 된 첫 번째 링크에 사용 된 동일한 문자열 예제 (babcbabcbaccba)에 대한 시각화가 있습니다.
이 링크 외에도 다음 위치에서 코드를 찾았습니다.
http://algs4.cs.princeton.edu/53substring/Manacher.java.html
이 알고리즘의 핵심을 이해하려는 다른 사람들에게 도움이되기를 바랍니다.
전체 기사 : http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/
우선 몇 가지 흥미로운 특성을 찾기 위해 회문을 면밀히 관찰 해 보겠습니다. 예를 들어, S1 = "abaaba"및 S2 = "abcba", 둘 다 회문이지만 둘 사이의 사소하지 않은 (즉, 길이 또는 문자가 아님) 차이점은 무엇입니까? S1은 i = 2와 i = 3 (존재하지 않는 공간!) 사이의 보이지 않는 공간을 중심으로 한 회문입니다. 반면에 S2는 i = 2 (즉, c)에서 문자를 중심으로합니다. 홀수 / 짝수 길이에 관계없이 회 문의 중심을 정중하게 처리하기 위해 문자 사이에 특수 문자 $를 삽입하여 회문을 변환합니다. 그러면 S1 = "abba"및 S2 = "abcba"가 i = 6 및 T2 = "$ a $ b $ c $ b를 중심으로하는 T1 ="$ a $ b $ a $ a $ b $ a $ "로 변환됩니다. $ a $ "는 i = 5를 중심으로합니다. 이제 중심이 존재하고 길이가 2 * n + 1로 일정하다는 것을 알 수 있습니다. 여기서 n은 원래 문자열의 길이입니다. 예를 들면
나는 ci
-------------------------------------------------- ---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
-------------------------------------------------- ---
T1 = | $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
-------------------------------------------------- ---
다음으로, 중심 c 주변의 (변환 된) 회문 T의 대칭 속성에서 0 <= k <= c에 대해 T [ck] = T [c + k]를 관찰합니다. 즉, 위치 ck와 c + k는 서로 거울입니다. 즉, 중심 c의 오른쪽에있는 인덱스 i의 경우 미러 인덱스 i '가 c의 왼쪽에 있으므로 c-i'= ic => i '= 2 * ci이고 그 반대의 경우도 마찬가지입니다. 그건,
회문 부분 문자열의 중앙 c 오른쪽에있는 각 위치 i에 대해 i의 미러 위치는 i '= 2 * ci이고 그 반대의 경우도 마찬가지입니다.
P [i]가 i를 중심으로하는 회 문의 길이와 같도록 배열 P [0..2 * n]을 정의합시다. 길이는 실제로 원래 문자열의 문자 수로 측정됩니다 (특수 문자 $ 무시). 또한 min과 max를 각각 c를 중심으로하는 회문 부분 문자열의 가장 왼쪽과 가장 오른쪽 경계가되도록합니다. 따라서 min = cP [c] 및 max = c + P [c]입니다. 예를 들어 회문 S = "abaaba"의 경우 변환 된 회문 T, 거울 중심 c = 6, 길이 배열 P [0..12], min = cP [c] = 6-6 = 0, max = c + P [c] = 6 + 6 = 12 및 두 개의 샘플 미러링 인덱스 i 및 i '가 다음 그림에 나와 있습니다.
min i 'ci max
-------------------------------------------------- ---
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
-------------------------------------------------- ---
T = | $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
-------------------------------------------------- ---
P = | 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
-------------------------------------------------- ---
이러한 길이 배열 P를 사용하면 P의 최대 요소를 조사하여 가장 긴 회문 부분 문자열의 길이를 찾을 수 있습니다. 즉,
P [i]는 변환 된 문자열 T에서 i를 중심으로하는 회문 부분 문자열의 길이입니다. 원래 문자열 S의 i / 2에서 중심; 따라서 가장 긴 회문 부분 문자열은 인덱스 (i max -P [i max ]) / 2 에서 시작 하는 길이 P [i max ] 의 부분 문자열이 되어 i max 가 P에서 최대 요소의 인덱스가됩니다.
비회 문적 예제 문자열 S = "babaabca"에 대해 다음과 유사한 그림을 그리겠습니다.
최소 c 최대
| ---------------- | ----------------- |
-------------------------------------------------- ------------------
idx = | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
-------------------------------------------------- -------------------
T = | $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
-------------------------------------------------- -------------------
P = | 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
-------------------------------------------------- -------------------
질문은 P를 효율적으로 계산하는 방법입니다. 대칭 속성은 왼쪽의 미러 인덱스 i '에서 이전에 계산 된 P [i']를 사용하여 많은 계산을 건너 뛰어 P [i]를 계산하는 데 잠재적으로 사용할 수있는 다음 경우를 제안합니다. 시작할 참조 회문 (첫 번째 회문)이 있다고 가정 해 봅시다.
-
중앙이 첫 번째 회 문의 오른쪽 내에있는 세 번째 회 문의 길이는 두 번째 회문이 at에 의해 첫 번째 회 문의 경계 내에있는 경우 왼쪽의 거울 중앙에 고정 된 두 번째 회 문의 길이와 정확히 동일합니다. 최소한 한 문자.
예를 들어, c = 8을 중심으로하고 min = 4 및 max = 12로 경계가 지정된 첫 번째 회문이있는 다음 그림에서 i = 9 (미러 인덱스 i '= 2 * ci = 7)를 중심으로하는 세 번째 회 문의 길이는 다음과 같습니다. , P [i] = P [i '] = 1. 이것은 i'를 중심으로하는 두 번째 회문이 첫 번째 회 문의 경계 내에 있기 때문입니다. 마찬가지로 P [10] = P [6] = 0입니다.| ---- 3 일 ---- | | ---- 2 위 ---- | | ----------- 제 1 회문 --------- | min i 'ci max | ------------ | --- | --- | ------------- | -------------------------------------------------- ------------------ idx = | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | -------------------------------------------------- ------------------- T = | $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ | -------------------------------------------------- ------------------- P = | 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? | -------------------------------------------------- -------------------자,이 사건을 어떻게 확인 하느냐는 질문입니다. 대칭 속성으로 인해 세그먼트 [min..i ']의 길이는 세그먼트 [i..max]의 길이와 같습니다. 또한, 두 번째 회 문의 왼쪽 가장자리가 첫 번째 회 문의 분인 왼쪽 경계 안에있는 경우 두 번째 회문은 완전히 첫 번째 회문 내에 있습니다. 그건,i'-P [i ']> = 분 => P [i ']-i'<-min (부정) => P [i '] <i'-min => P [i '] <max-i [(max-i) = (i'-min) due to symmetric property].케이스 1의 모든 사실을 결합하면P [i] = P [i '], iff (최대 -i)> P [i']
-
두 번째 회문이 첫 번째 회 문의 왼쪽 경계와 만나거나 그 이상으로 확장되면 세 번째 회문은 적어도 자체 중심에서 첫 번째 회 문의 가장 오른쪽 바깥 쪽 문자까지의 길이가 보장됩니다. 이 길이는 두 번째 회 문의 중심에서 첫 번째 회 문의 가장 왼쪽 바깥 쪽 문자까지 동일합니다.
예를 들어 다음 그림에서 i = 5를 중심으로하는 두 번째 회문은 첫 번째 회 문의 왼쪽 경계를 넘어 확장됩니다. 따라서이 경우에는 P [i] = P [i ']라고 말할 수 없습니다. 그러나 i = 11을 중심으로하는 세 번째 회 문의 길이, P [i]는 적어도 중심 i = 11에서 c를 중심으로 한 첫 번째 회 문의 오른쪽 경계 max = 12까지의 길이입니다. 즉, P [i]> = 1입니다. 이것은 세 번째 회문이 max를 지나서 바로 다음 문자가 미러링 된 문자와 정확히 일치하는 경우에만 최대를 넘어 확장 될 수 있음을 의미하며, 우리는이 검사를 계속합니다. 예를 들어이 경우 P [13]! = P [9]이며 확장 할 수 없습니다. 따라서 P [i] = 1입니다.| ------- 두 번째 회문 ------ | | ---- 3 일 ---- | ---? | ----------- 제 1 회문 --------- | min i 'ci max | ---- | ----------- | ----------- | ----- | -------------------------------------------------- ------------------ idx = | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | -------------------------------------------------- ------------------- T = | $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ | -------------------------------------------------- ------------------- P = | 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? | -------------------------------------------------- -------------------그렇다면이 사건을 어떻게 확인합니까? 이것은 단순히 사례 1에 대한 실패한 검사입니다. 즉, 두 번째 회문이 첫 번째 회 문의 왼쪽 가장자리를지나 확장됩니다.i'-P [i '] <min => P [i ']-i'> = -min [부정] => P [i ']> = i'-min => P [i ']> = max-i [(max-i) = (i'-min) by symmetric property].즉, P [i]는 적어도 (max-i) iff (max-i) P [i]> = (max-i), iff (max-i) 이제 세 번째 회문이 max 이상으로 확장되면 새로운 회 문의 중심과 경계를 업데이트해야합니다.i를 중심으로 한 회문이 최대를 넘어 확장되면 새로운 (확장 된) 회문이 있으므로 c = i에 새로운 중심이 있습니다. 새 회 문의 가장 오른쪽 경계까지 최대 값을 업데이트합니다.
사례 1과 사례 2의 모든 사실을 결합하면 매우 아름다운 작은 공식을 만들 수 있습니다.사례 1 : P [i] = P [i '], iff (최대 -i)> P [i'] 사례 2 : P [i]> = (max-i), iff (max-i) = min (P [i '], max-i).즉, P [i] = min (P [i '], max-i) 세 번째 회문이 max를지나 연장 할 수 없을 때. 그렇지 않으면 중앙에 c = i 및 new max = i + P [i]에 새로운 세 번째 회문이 있습니다.
-
첫 번째 회문과 두 번째 회문은 중심이 첫 번째 회 문의 오른쪽 밖에있는 네 번째 회 문의 회문 길이를 결정하는 데 도움이되는 정보를 제공하지 않습니다.
즉, i> max이면 선제 적으로 P [i]를 결정할 수 없습니다. 그건,P [i] = 0, iff max-i <0
모든 경우를 결합하여 공식을 결론지었습니다.P [i] = 최대> i? min (P [i '], max-i) : 0. max를 넘어서 확장 할 수있는 경우 c = i의 새로운 중심에 대해 미러링 된 문자와 max를 넘어선 문자를 일치시켜 확장합니다. 마지막으로 불일치가 발생하면 새로운 max = i + P [i]를 업데이트합니다.
참조 : 위키 페이지의 알고리즘 설명
애니메이션 그래픽을 사용하여이 알고리즘에 대한 비디오를 만들었습니다. 이해하는 데 도움이되기를 바랍니다. https://www.youtube.com/watch?v=kbUiR5YWUpQ
이 자료는 제가 이해하는 데 큰 도움이됩니다 : http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html
T를 각 문자 중심에있는 가장 긴 회문 부분 문자열의 길이로 정의합니다.
핵심은 더 작은 회문이 더 긴 회문 내에 완전히 박혀있을 때 T [i]도 긴 회문 내에서 대칭이어야한다는 것입니다.
그렇지 않으면 대칭 왼쪽 부분에서 유도하는 대신 처음부터 T [i]를 계산해야합니다.
class Palindrome
{
private int center;
private int radius;
public Palindrome(int center, int radius)
{
if (radius < 0 || radius > center)
throw new Exception("Invalid palindrome.");
this.center = center;
this.radius = radius;
}
public int GetMirror(int index)
{
int i = 2 * center - index;
if (i < 0)
return 0;
return i;
}
public int GetCenter()
{
return center;
}
public int GetLength()
{
return 2 * radius;
}
public int GetRight()
{
return center + radius;
}
public int GetLeft()
{
return center - radius;
}
public void Expand()
{
++radius;
}
public bool LargerThan(Palindrome other)
{
if (other == null)
return false;
return (radius > other.radius);
}
}
private static string GetFormatted(string original)
{
if (original == null)
return null;
else if (original.Length == 0)
return "";
StringBuilder builder = new StringBuilder("#");
foreach (char c in original)
{
builder.Append(c);
builder.Append('#');
}
return builder.ToString();
}
private static string GetUnFormatted(string formatted)
{
if (formatted == null)
return null;
else if (formatted.Length == 0)
return "";
StringBuilder builder = new StringBuilder();
foreach (char c in formatted)
{
if (c != '#')
builder.Append(c);
}
return builder.ToString();
}
public static string FindLargestPalindrome(string str)
{
string formatted = GetFormatted(str);
if (formatted == null || formatted.Length == 0)
return formatted;
int[] radius = new int[formatted.Length];
try
{
Palindrome current = new Palindrome(0, 0);
for (int i = 0; i < formatted.Length; ++i)
{
radius[i] = (current.GetRight() > i) ?
Math.Min(current.GetRight() - i, radius[current.GetMirror(i)]) : 0;
current = new Palindrome(i, radius[i]);
while (current.GetLeft() - 1 >= 0 && current.GetRight() + 1 < formatted.Length &&
formatted[current.GetLeft() - 1] == formatted[current.GetRight() + 1])
{
current.Expand();
++radius[i];
}
}
Palindrome largest = new Palindrome(0, 0);
for (int i = 0; i < radius.Length; ++i)
{
current = new Palindrome(i, radius[i]);
if (current.LargerThan(largest))
largest = current;
}
return GetUnFormatted(formatted.Substring(largest.GetLeft(), largest.GetLength()));
}
catch (Exception ex)
{
Console.WriteLine(ex);
}
return null;
}
문자열에서 가장 긴 회문을 찾는 빠른 자바 스크립트 솔루션 :
const lpal = str => {
let lpal = ""; // to store longest palindrome encountered
let pal = ""; // to store new palindromes found
let left; // to iterate through left side indices of the character considered to be center of palindrome
let right; // to iterate through left side indices of the character considered to be center of palindrome
let j; // to iterate through all characters and considering each to be center of palindrome
for (let i=0; i<str.length; i++) { // run through all characters considering them center of palindrome
pal = str[i]; // initializing current palindrome
j = i; // setting j as index at the center of palindorme
left = j-1; // taking left index of j
right = j+1; // taking right index of j
while (left >= 0 && right < str.length) { // while left and right indices exist
if(str[left] === str[right]) { //
pal = str[left] + pal + str[right];
} else {
break;
}
left--;
right++;
}
if(pal.length > lpal.length) {
lpal = pal;
}
pal = str[i];
j = i;
left = j-1;
right = j+1;
if(str[j] === str[right]) {
pal = pal + str[right];
right++;
while (left >= 0 && right < str.length) {
if(str[left] === str[right]) {
pal = str[left] + pal + str[right];
} else {
break;
}
left--;
right++;
}
if(pal.length > lpal.length) {
lpal = pal;
}
}
}
return lpal;
}
예제 입력
console.log(lpal("gerngehgbrgregbeuhgurhuygbhsbjsrhfesasdfffdsajkjsrngkjbsrjgrsbjvhbvhbvhsbrfhrsbfsuhbvsuhbvhvbksbrkvkjb"));
산출
asdfffdsa
using namespace std;
class Palindrome{
public:
Palindrome(string st){
s = st;
longest = 0;
maxDist = 0;
//ascii: 126(~) - 32 (space) = 94
// for 'a' to 'z': vector<vector<int>> v(26,vector<int>(0));
vector<vector<int>> v(94,vector<int>(0)); //all ascii
mDist.clear();
vPos = v;
bDebug = true;
};
string s;
string sPrev; //previous char
int longest; //longest palindrome size
string sLongest; //longest palindrome found so far
int maxDist; //max distance been checked
bool bDebug;
void findLongestPal();
int checkIfAnchor(int iChar, int &i);
void checkDist(int iChar, int i);
//store char positions in s pos[0] : 'a'... pos[25] : 'z'
// 0123456
// i.e. "axzebca" vPos[0][0]=0 (1st. position of 'a'), vPos[0][1]=6 (2nd pos. of 'a'),
// vPos[25][0]=2 (1st. pos. of 'z').
vector<vector<int>> vPos;
//<anchor,distance to check>
// i.e. abccba anchor = 3: position of 2nd 'c', dist = 3
// looking if next char has a dist. of 3 from previous one
// i.e. abcxcba anchor = 4: position of 2nd 'c', dist = 4
map<int,int> mDist;
};
//check if current char can be an anchor, if so return next distance to check (3 or 4)
// i.e. "abcdc" 2nd 'c' is anchor for sub-palindrome "cdc" distance = 4 if next char is 'b'
// "abcdd: 2nd 'd' is anchor for sub-palindrome "dd" distance = 3 if next char is 'c'
int Palindrome::checkIfAnchor(int iChar, int &i){
if (bDebug)
cout<<"checkIfAnchor. i:"<<i<<" iChar:"<<iChar<<endl;
int n = s.size();
int iDist = 3;
int iSize = vPos[iChar].size();
//if empty or distance to closest same char > 2
if ( iSize == 0 || vPos[iChar][iSize - 1] < (i - 2)){
if (bDebug)
cout<<" .This cannot be an anchor! i:"<<i<<" : iChar:"<<iChar<<endl;
//store char position
vPos[iChar].push_back(i);
return -1;
}
//store char position of anchor for case "cdc"
vPos[iChar].push_back(i);
if (vPos[iChar][iSize - 1] == (i - 2))
iDist = 4;
//for case "dd" check if there are more repeated chars
else {
int iRepeated = 0;
while ((i+1) < n && s[i+1] == s[i]){
i++;
iRepeated++;
iDist++;
//store char position
vPos[iChar].push_back(i);
}
}
if (bDebug)
cout<<" .iDist:"<<iDist<<" i:"<<i<<endl;
return iDist;
};
//check distance from previous same char, and update sLongest
void Palindrome::checkDist(int iChar, int i){
if (bDebug)
cout<<"CheckDist. i:"<<i<<" iChar:"<<iChar<<endl;
int iDist;
int iSize = vPos[iChar].size();
bool b1stOrLastCharInString;
bool bDiffDist;
//checkAnchor will add this char position
if ( iSize == 0){
if (bDebug)
cout<<" .1st time we see this char. Assign it INT_MAX Dist"<<endl;
iDist = INT_MAX;
}
else {
iDist = i - vPos[iChar][iSize - 1];
}
//check for distances being check, update them if found or calculate lengths if not.
if (mDist.size() == 0) {
if (bDebug)
cout<<" .no distances to check are registered, yet"<<endl;
return;
}
int i2ndMaxDist = 0;
for(auto it = mDist.begin(); it != mDist.end();){
if (bDebug)
cout<<" .mDist. anchor:"<<it->first<<" . dist:"<<it->second<<endl;
b1stOrLastCharInString = false;
bDiffDist = it->second == iDist; //check here, because it can be updated in 1st. if
if (bDiffDist){
if (bDebug)
cout<<" .Distance checked! :"<<iDist<<endl;
//check if it's the first char in the string
if (vPos[iChar][iSize - 1] == 0 || i == (s.size() - 1))
b1stOrLastCharInString = true;
//we will continue checking for more...
else {
it->second += 2; //update next distance to check
if (it->second > maxDist) {
if (bDebug)
cout<<" .previous MaxDist:"<<maxDist<<endl;
maxDist = it->second;
if (bDebug)
cout<<" .new MaxDist:"<<maxDist<<endl;
}
else if (it->second > i2ndMaxDist) {//check this...hmtest
i2ndMaxDist = it->second;
if (bDebug)
cout<<" .second MaxDist:"<<i2ndMaxDist<<endl;
}
it++;
}
}
if (!bDiffDist || b1stOrLastCharInString) {
if (bDebug && it->second != iDist)
cout<<" .Dist diff. Anchor:"<<it->first<<" dist:"<<it->second<<" iDist:"<<iDist<<endl;
else if (bDebug)
cout<<" .Palindrome found at the beggining or end of the string"<<endl;
//if we find a closest same char.
if (!b1stOrLastCharInString && it->second > iDist){
if (iSize > 1) {
if (bDebug)
cout<<" . < Dist . looking further..."<<endl;
iSize--;
iDist = i - vPos[iChar][iSize - 1];
continue;
}
}
if (iDist == maxDist) {
maxDist = 0;
if (bDebug)
cout<<" .Diff. clearing Max Dist"<<endl;
}
else if (iDist == i2ndMaxDist) {
i2ndMaxDist = 0;
if (bDebug)
cout<<" .clearing 2nd Max Dist"<<endl;
}
int iStart;
int iCurrLength;
//first char in string
if ( b1stOrLastCharInString && vPos[iChar].size() > 0 && vPos[iChar][iSize - 1] == 0){
iStart = 0;
iCurrLength = i+1;
}
//last char in string
else if (b1stOrLastCharInString && i == (s.size() - 1)){
iStart = i - it->second;
iCurrLength = it->second + 1;
}
else {
iStart = i - it->second + 1;
iCurrLength = it->second - 1; //"xabay" anchor:2nd. 'a'. Dist from 'y' to 'x':4. length 'aba':3
}
if (iCurrLength > longest){
if (bDebug)
cout<<" .previous Longest!:"<<sLongest<<" length:"<<longest<<endl;
longest = iCurrLength;
sLongest = s.substr(iStart, iCurrLength);
if (bDebug)
cout<<" .new Longest!:"<<sLongest<<" length:"<<longest<<endl;
}
if (bDebug)
cout<<" .deleting iterator for anchor:"<<it->first<<" dist:"<<it->second<<endl;
mDist.erase(it++);
}
}
//check if we need to get new max distance
if (maxDist == 0 && mDist.size() > 0){
if (bDebug)
cout<<" .new maxDist needed";
if (i2ndMaxDist > 0) {
maxDist = i2ndMaxDist;
if (bDebug)
cout<<" .assigned 2nd. max Dist to max Dist"<<endl;
}
else {
for(auto it = mDist.begin(); it != mDist.end(); it++){
if (it->second > maxDist)
maxDist = it->second;
}
if (bDebug)
cout<<" .new max dist assigned:"<<maxDist<<endl;
}
}
};
void Palindrome::findLongestPal(){
int n = s.length();
if (bDebug){
cout<<"01234567891123456789212345"<<endl<<"abcdefghijklmnopqrstuvwxyz"<<endl<<endl;
for (int i = 0; i < n;i++){
if (i%10 == 0)
cout<<i/10;
else
cout<<i;
}
cout<<endl<<s<<endl;
}
if (n == 0)
return;
//process 1st char
int j = 0;
//for 'a' to 'z' : while (j < n && (s[j] < 'a' && s[j] > 'z'))
while (j < n && (s[j] < ' ' && s[j] > '~'))
j++;
if (j > 0){
s.substr(j);
n = s.length();
}
// for 'a' to 'z' change size of vector from 94 to 26 : int iChar = s[0] - 'a';
int iChar = s[0] - ' ';
//store char position
vPos[iChar].push_back(0);
for (int i = 1; i < n; i++){
if (bDebug)
cout<<"findLongestPal. i:"<<i<<" "<<s.substr(0,i+1)<<endl;
//if max. possible palindrome would be smaller or equal
// than largest palindrome found then exit
// (n - i) = string length to check
// maxDist: max distance to check from i
int iPossibleLongestSize = maxDist + (2 * (n - i));
if ( iPossibleLongestSize <= longest){
if (bDebug)
cout<<" .PosSize:"<<iPossibleLongestSize<<" longest found:"<<iPossibleLongestSize<<endl;
return;
}
//for 'a' to 'z' : int iChar = s[i] - 'a';
int iChar = s[i] - ' ';
//for 'a' to 'z': if (iChar < 0 || iChar > 25){
if (iChar < 0 || iChar > 94){
if (bDebug)
cout<<" . i:"<<i<<" iChar:"<<s[i]<<" skipped!"<<endl;
continue;
}
//check distance to previous char, if exist
checkDist(iChar, i);
//check if this can be an anchor
int iDist = checkIfAnchor(iChar,i);
if (iDist == -1)
continue;
//append distance to check for next char.
if (bDebug)
cout<<" . Adding anchor for i:"<<i<<" dist:"<<iDist<<endl;
mDist.insert(make_pair(i,iDist));
//check if this is the only palindrome, at the end
//i.e. "......baa" or "....baca"
if (i == (s.length() - 1) && s.length() > (iDist - 2)){
//if this is the longest palindrome!
if (longest < (iDist - 1)){
sLongest = s.substr((i - iDist + 2),(iDist - 1));
}
}
}
};
int main(){
string s;
cin >> s;
Palindrome p(s);
p.findLongestPal();
cout<<p.sLongest;
return 0;
}
'Programing' 카테고리의 다른 글
| 기록이있는 저장소 간 SVN 사본 (0) | 2020.11.09 |
|---|---|
| 그룹 별 사용과 구별 사용시 큰 성능 차이 (0) | 2020.11.09 |
| R의 python dict에 해당 (0) | 2020.11.09 |
| PostgreSQL과 MySQL은 얼마나 다른가요? (0) | 2020.11.09 |
| 사소한 vs. 표준 레이아웃 vs. POD (0) | 2020.11.09 |