정의
회문(Palindrome)은 똑바로 읽어도 거꾸로 읽어도 같은 문자열을 의미한다.
ex. 기러기, 토마토, 스위스, 인도인, 별똥별 …
회문 판별 알고리즘
회문 판별을 위한 가장 직관적인 방법은 첫 문자와 끝 문자부터 시작하여 안쪽으로 차례차례 비교하는 것이다.
bool isPalindrome(string s) {
int size = s.size();
for(int i = 0; i< size/2; i++) {
if(s[i] != s[size-1-i])
return false;
}
return true;
}이 경우 문자열이 회문인 경우 N/2 번의 반복문이 실행되므로 의 시간복잡도를 갖는다.
부분 문자열 회문 찾기 알고리즘
주어진 문자열이 있을 때, 부분 문자열 중 회문인 문자열을 찾는 알고리즘이다.
예를 들어 colossus 이라는 문자열이 주어진다면, 이 문자열의 부분 문자열 중 회문인 문자열은 c, o, l, s, u, olo, ss, sus 이다.
By Brute Force
가장 간단한 해결책은 존재하는 모든 부분문자열에 대해 회문인지에 대한 여부를 검사하는 것이다.
void printPalindromicSubstrings(string s) {
unordered_set<string> set;
for(int i=0; i<s.size(); i++) {
for(int j=1; j <= s.size()-i ;j++) {
string substring = s.substr(i,j);
if(isPalindrome(substring))
set.insert(substring);
}
}
for (auto s: set) {
cout << s << " ";
}
}위 코드에서는 2개의 for문이 존재한다.
첫번째 for문은 부분문자열이 시작될 인덱스를 결정한다.
두번째 for문은 시작 인덱스에서 추출할 부분 문자열의 길이를 결정한다.
문자열의 길이가 N일 때, 첫번째 for문과 두번째 for문에 의해서 번의 isPalindrome 메서드가 수행되고, isPalindrome 메서드는 을 가지므로 결과적으로 의 시간복잡도를 가지게 된다.
By Dynamic Programming
다이나믹 프로그래밍을 사용하여 시간복잡도를 로 줄일 수 있다.
다이나믹 프로그래밍을 위한 일반화된 공식은 다음과 같다.
- dp[i][j] 가 1이라는 것은 i 번 인덱스부터 j번 인덱스까지의 문자열이 회문이라는 것을 의미한다.
- 따라서 dp[m][m] 은 모두 1을 갖는다. (자기 자신은 모두 회문이다.)
- 또한 string[n] 과 string[n+1] 이 같다면, dp[n][n+1] 은 1을 갖는다. ( “aa” 나 “cc” 의 경우를 의미한다.)
- 만약 string[i] 와 string[j] 가 같을 때, dp[i+1][j-1] 가 회문이라면 dp[i][j] 역시 1을 갖는다.
위 규칙을 사용해서 작성한 코드는 아래와 같다.
bool dp[1000][1000]; //false initialization
void printPalindromicSubstrings(string s) {
unordered_set<string> set;
for(int i=0; i<s.size(); i++) {
dp[i][i] = true;
set.insert(s.substr(i,1));
}
for(int i=0; i<s.size() - 1; i++) {
if(s[i] == s[i+1]) {
dp[i][i+1] = true;
set.insert(s.substr(i,2));
}
}
for(int k = 2; k <= s.size() - 1 ; k++) {
for(int i = 0; i < s.size() - k; i++) {
int j = i + k;
if((s[i] == s[j])&&(dp[i+1][j-1])) {
dp[i][j] = true;
set.insert(s.substr(i,k+1));
}
}
}
for (auto s: set) {
cout << s << " ";
}
}
By Manacher’s Algorithm
Mancher’s Algorithm 을 사용한다면 시간복잡도를 으로 낮출 수 있다.
Manacher's algorithm
Manacher's algorithm은 각 문자를 중심으로 하는 팔린드롬을 측정하기 때문에, 길이가 짝수인 팔린드롬은 찾을 수 없다. (예:abcddcba) 각 글자 사이에 더미 문자를 끼워넣어서 'a#b#c#d#d#c#b#a'꼴로 만들고 풀면, 짝수길이인 팔린드롬 역시 찾을 수 있다.
Uploaded by N2T