[algorithm] 주어진 문자열에서 가장 긴 회문을 반환하는 함수 작성

예 : “abaccddccefe”문자열의 “ccddcc”

해결책을 생각했지만 O (n ^ 2) 시간에 실행됩니다.

알고 1 :

단계 : 무차별 대입 방법

  1. i = 1 ~ i에 대해 2 개의 for 루프 가 array.length보다 작습니다.
    j = i + 1 ~ j가 array.length보다 작 으면 -1 입니다.
  2. 이렇게하면 배열에서 가능한 모든 조합의 하위 문자열을 얻을 수 있습니다.
  3. 문자열이 회문인지 확인하는 회문 기능이 있습니다.
  4. 따라서 모든 하위 문자열 (i, j)에 대해이 함수를 호출합니다. 회문이면 문자열 변수에 저장합니다.
  5. 다음 회문 부분 문자열을 찾고 현재 문자열보다 크면 현재 문자열로 바꿉니다.
  6. 마지막으로 문자열 변수에 답이 있습니다.

문제 : 1.이 알고리즘은 O (n ^ 2) 시간에 실행됩니다.

알고 2 :

  1. 문자열을 뒤집어 다른 배열에 저장하십시오.
  2. 이제 두 배열 사이에서 가장 일치하는 부분 문자열을 찾으십시오.
  3. 하지만 이것도 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;
  }