마나커 (팰린드롬)

길이가 홀수인 문자열 s에 대해 다음을 O(n)에 구할 수 있다. 길이가 짝수인 문자열은 중간에 더미문자를 추가해준다.

 

dp[i] : s[i]를 중심으로 하는 가장 긴 팰린드롬의 반지름

(예를들어, s : aba  -> dp : 0 1 0)

 

n = s.size()

i : [0~n-1] 순서대로 초기화 할 것.

0~i-1까지 팰린드롬 중 가장 우측의 오른쪽 경계 r과 그때의 인덱스 k을 이용해서 dp[i]초기화

 

다음과같이 경우를 나누어 초기화해 준다.

1) i<=r 

i의 점을 k에 대해 대칭시킨 점 p. (p+i = 2*k -> p= 2*k-i)

 

1-1)

p를 중심으로 하는 가장 긴 팰린드롬이 k를 중심으로 하는 가장 긴 팰린드롬에 속하는 경우

dp[i] = dp[p]

 

1-2)

p를 중심으로 하는 가장 긴 팰린드롬이 k를 중심으로 하는 가장 긴 팰린드롬의 왼쪽으로 경계를 넘는 경우

dp[i] = i~r까지 거리 = r-i

 

2) i>r

while문을 이용해서 직접 찾아줘야 한다. 

i-dp[i]-1, i+dp[i]+1번째가 같은지 탐색하며 dp[i]를 1씩 올려주면 된다.

 

<코드>

string t,s;
int dp[MAX], n, r=-1, k=-1;

int main() {
	FAST; cin >> s;
		
	n = s.size();
	for (int i = 0; i < n; i++) {
		if (i <= r) dp[i] = min(r - i, dp[2 * k - i]);
		while (i - dp[i] - 1 >= 0 && i + dp[i] + 1 < n && s[i - dp[i] - 1] == s[i + dp[i] + 1])
			dp[i]++;
		if (r < i + dp[i]) r = i + dp[i], k = i;
	}
}

 

<생각>

while문떄문에 O(n제곱)이지 않은가?

-> r이 0~n-1까지 이동하는 그림을 생각해보면 전체 O(n)이다. 밑 블로그 참고

 

 

참고:

https://namnamseo.tistory.com/entry/%EC%A0%84%EC%B2%B4-%EB%AC%B8%EC%9E%90%EC%97%B4%EC%97%90%EC%84%9C-palindrome%EC%9D%98-%EA%B0%AF%EC%88%98-%EC%84%B8%EA%B8%B0-ON

 

---

 

<문제1>

길이가 최대 1e6인 문자열 s가 주어진다.

이 문자의 접두사이며 팰린드롬인 것 중 길이가 최대인 문자열을 출력

 

input:  abacd,   adcda,   addc,   addaac

output: aba, adcda, a, adda

 

<풀이>

우선 더미문자 추가한 문자열 t에 대해 dp배열을 초기화해준다.

 

i-dp[i] == 0인것 중 i+dp[i]가 최대인 경우가 그 팰린드롬의 길이이다.

 

#을 빼고 출력해주면 된다.

 

<코드>

string s,t;
int n, dp[MAX];

int main() {
	FAST; cin >> s;
	for (int i = 0; i < s.size(); i++) {
		t.push_back(s[i]);
		if (i != s.size()-1) t.push_back('#');
	}
	n = t.size();

	int r = -1, k = -1;
	for (int i = 0; i < n; i++) {
		if (i <= r) dp[i] = min(dp[2 * k - i], r - i);
		while (i + dp[i] + 1 < n && i - dp[i] - 1 >= 0 && t[i + dp[i] + 1] == t[i - dp[i] - 1])
			dp[i]++;
		if (r < i + dp[i]) r = i + dp[i], k = i;
	}

	int ans = 0;
	for (int i = 1; i < n; i++) 
		if (i - dp[i] == 0) 
			ans = i + dp[i];

	s = t.substr(0, ans + 1);
	for (int i = 0; i < s.size(); i++) if (s[i] != '#')
		cout << s[i];
	cout << '\n';
}

https://suuntree.tistory.com/213

위 문제를 이 방법을 응용해서 풀 수 있다.