풀이 1 / DP 사용 안함
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <stdio.h> #include <string> #include <iostream> using namespace std; string str; int main() { cin >> str; str = "0" + str; int len = str.length() - 1; int part; for (int i = 1; i <= len; i++) { if (str[i] == str[len]) { int d; for (d = 0; i + d < len - d; d++) { if (str[i + d] != str[len - d]) { break; } } if (i + d == len - d) { part = 2 * d + 1; break; } else if (i + d > len - d) { part = 2 * d; break; } } } printf("%d", len + (len - part)); } | cs |
풀이2 / DP 사용
출처) (https://algospot.com/wiki/read/Manacher's_algorithm)
#include <iostream>
#include <string>
#include <cstring> //memset
using namespace std;
const int MAX = 1000;
string S;
int length;
bool palindrome(int idx)
{
for (int i = 0; idx + i < length - i - 1; i++)
//하나라도 성립안하면 palindrome 아님
if (S[idx + i] != S[length - i - 1])
return false;
return true;
}
int main(void)
{
cin >> S;
length = S.size();
int result = 0;
//1. 주어진 문자열의 길이 length일 때 palindrome 되는지 확인
//2. 1번이 성립 안되면 length+1일 때 palindrome 되는지 확인
//length - 2 까지 계속 확인 ...
//length-1. length-2번이 성립 안되면 length+length-1일 때 palindrome
for(int i=0; i<length; i++)
if (palindrome(i))
{
result = length + i;
break;
}
cout << result << endl;
return 0;
}
'알고리즘 > DP' 카테고리의 다른 글
| 1509 펠린드롬 분할 (0) | 2019.07.13 |
|---|---|
| 10844 쉬운 계단수 (0) | 2019.07.13 |
| 1958 LCS3 (0) | 2019.07.13 |
| 5582 공통부분 문자열 (0) | 2019.07.13 |
| 3943 헤일스톤 수열 (0) | 2019.07.12 |