[algorithm] 주어진 문자열에서 가장 긴 회문을 반환하는 함수 작성
예 : “abaccddccefe”문자열의 “ccddcc”
해결책을 생각했지만 O (n ^ 2) 시간에 실행됩니다.
알고 1 :
단계 : 무차별 대입 방법
-
i = 1 ~ i에 대해 2 개의 for 루프 가 array.length보다 작습니다.
j = i + 1 ~ j가 array.length보다 작 으면 -1 입니다. - 이렇게하면 배열에서 가능한 모든 조합의 하위 문자열을 얻을 수 있습니다.
- 문자열이 회문인지 확인하는 회문 기능이 있습니다.
- 따라서 모든 하위 문자열 (i, j)에 대해이 함수를 호출합니다. 회문이면 문자열 변수에 저장합니다.
- 다음 회문 부분 문자열을 찾고 현재 문자열보다 크면 현재 문자열로 바꿉니다.
- 마지막으로 문자열 변수에 답이 있습니다.
문제 : 1.이 알고리즘은 O (n ^ 2) 시간에 실행됩니다.
알고 2 :
- 문자열을 뒤집어 다른 배열에 저장하십시오.
- 이제 두 배열 사이에서 가장 일치하는 부분 문자열을 찾으십시오.
- 하지만 이것도 O (n ^ 2) 시간에 실행됩니다.
더 나은 시간에 실행되는 알고리즘을 생각할 수 있습니까? 가능하면 O (n) 시간
답변
Manacher ‘s Algorithm 을 사용하여 가장 긴 회문을 찾을 수 있습니다 O(n)! 구현은 여기 와 여기 에서 찾을 수 있습니다 .
입력의 String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"경우 올바른 출력을 찾습니다 1234567887654321.
답변
Algo 2는 모든 문자열에서 작동하지 않을 수 있습니다. 다음은 이러한 문자열 “ABCDEFCBA”의 예입니다.
문자열의 하위 문자열로 “ABC”및 “CBA”가있는 것은 아닙니다. 원래 문자열을 반대로하면 “ABCFEDCBA”가됩니다. 가장 긴 일치하는 부분 문자열은 회문이 아닌 “ABC”입니다.
이 가장 긴 일치 하위 문자열이 실제로 실행 시간이 O (n ^ 3) 인 회문인지 추가로 확인해야 할 수도 있습니다.
답변
내가 문제를 이해하는 한, 우리는 중앙 색인 주위에서 회문을 찾을 수 있고 중앙의 오른쪽과 왼쪽으로 검색 범위를 둘 수 있습니다. 입력의 모서리에 회문이 없다는 것을 알고 있으므로 경계를 1 및 길이 -1로 설정할 수 있습니다. String의 최소 및 최대 경계에주의를 기울이면서 대칭 인덱스 (오른쪽 및 왼쪽) 위치의 문자가 최대 상한 중심에 도달 할 때까지 각 중앙 위치에 대해 동일한 지 확인합니다.
외부 루프는 O (n) (최대 n-2 회 반복)이고 내부 while 루프는 O (n) (최대 약 (n / 2)-1 회 반복)
다음은 다른 사용자가 제공 한 예제를 사용한 Java 구현입니다.
class LongestPalindrome {
/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1; rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--; rightIndex++;
}
}
return longestPalindrome;
}
public static void main(String ... args) {
String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
이 결과는 다음과 같습니다.
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
답변
정규식과 루비를 사용하면 다음과 같은 짧은 회문을 스캔 할 수 있습니다.
PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w)\6\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w\4\3\2)/; p $1
"ranynar"
=> nil
답변
나는 호기심, 간단하고 자명 한 HTH로 다음 Java 프로그램을 작성했습니다. 감사.
/**
*
* @author sanhn
*/
public class CheckPalindrome {
private static String max_string = "";
public static void checkSubString(String s){
System.out.println("Got string is "+s);
for(int i=1;i<=s.length();i++){
StringBuilder s1 = new StringBuilder(s.substring(0,i));
StringBuilder s2 = new StringBuilder(s.substring(0,i));
s2.reverse();
if(s1.toString().equals(s2.toString())){
if(max_string.length()<=s1.length()){
max_string = s1.toString();
System.out.println("tmp max is "+max_string);
}
}
}
}
public static void main(String[] args){
String s="HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE";
for(int i=0; i<s.length(); i++)
checkSubString(s.substring(i, s.length()));
System.out.println("Max string is "+max_string);
}
}
답변
최근에이 질문을 받았습니다. 여기 내가 [결국] 생각 해낸 해결책이 있습니다. 해당 언어에서 매우 간단하기 때문에 JavaScript로했습니다.
기본 개념은 가능한 가장 작은 다중 문자 회문 (2 또는 3 문자)을 찾기 위해 현을 걷는 것입니다. 일단 그것이 회문이 될 때까지 양쪽의 경계를 확장하십시오. 그 길이가 현재 가장 긴 길이보다 길면 저장하고 따라 이동하십시오.
// This does the expanding bit.
function getsize(s, start, end) {
var count = 0, i, j;
for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
if (s[i] !== s[j]) {
return count;
}
count = j - i + 1; // keeps track of how big the palindrome is
}
return count;
}
function getBiggestPalindrome(s) {
// test for simple cases
if (s === null || s === '') { return 0; }
if (s.length === 1) { return 1; }
var longest = 1;
for (var i = 0; i < s.length - 1; i++) {
var c = s[i]; // the current letter
var l; // length of the palindrome
if (s[i] === s[i+1]) { // this is a 2 letter palindrome
l = getsize(s, i, i+1);
}
if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
l = getsize(s, i+1, i+1);
}
if (l > longest) { longest = l; }
}
return longest;
}
이것은 확실히 정리하고 조금 더 최적화 할 수 있지만 최악의 시나리오 (같은 문자의 문자열)를 제외한 모든 상황에서 꽤 좋은 성능을 가져야합니다.
답변
안녕 여기 문자열에서 가장 긴 회문을 찾는 코드가 있습니다. 알고리즘을 이해하려면 다음 링크를 참조하십시오. 참조하십시오. http://stevekrenzel.com/articles/longest-palnidrome
사용 된 테스트 데이터는 HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE입니다.
//Function GetPalindromeString
public static string GetPalindromeString(string theInputString)
{
int j = 0;
int k = 0;
string aPalindrome = string.Empty;
string aLongestPalindrome = string.Empty ;
for (int i = 1; i < theInputString.Length; i++)
{
k = i + 1;
j = i - 1;
while (j >= 0 && k < theInputString.Length)
{
if (theInputString[j] != theInputString[k])
{
break;
}
else
{
j--;
k++;
}
aPalindrome = theInputString.Substring(j + 1, k - j - 1);
if (aPalindrome.Length > aLongestPalindrome.Length)
{
aLongestPalindrome = aPalindrome;
}
}
}
return aLongestPalindrome;
}
