最長回文サブ文字列アルゴリズム

8125 ワード

エコー文字列
再帰的な実装
def is_palindrome(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and is_palindrome(s[1:-1])

(周知のように、再帰的な関数を書くには、終了として1つの基本的な状況が必要です.また、再帰的な状況も1つ必要です.
回文文字列の判断については、基本的には、1文字または空文字''、すなわちlen(s) <= 1の場合である.
再帰的な場合には、先頭の文字が同一であるか否か、すなわちs[0] == s[-1]を先に判断し、次に先頭の文字以外の文字であるis_palindrome(s[1:-1])を判断するようにしてもよい.
参考文献:1.10.練習:回文-『コンピュータ科学導論』学習ノート(22)-課程22:無限の力を持つ方法;2. 10. 練習:回文-課程22:どのように無限の力を持つか-『コンピュータ科学導論』-優達学城.
非再帰的実装
(回文文字列の非再帰的実装)
def iter_palindrome(s):
    for i in range(0, len(s) / 2):
        if s[i] != s[-(i+1)]:
            return False
    return True

(forサイクル中のif文の判断に注意してください.s[i] != s[-(i+1)]は外から内への遍歴、先頭文字が等しいかどうかを比較し、等しくない場合はFalseに戻ります.真ん中まで遍歴してもFalseに戻らない場合は、ループを終了します.つまり、文字列全体が回文文字列です.
ここでは,空文字列と単一文字に対する判断も暗黙的に含まれており,この2つの場合はループに入らず,Trueに直接戻る.
参考文献:1.11.再帰Vs反復-『コンピュータ科学導論』学習ノート(22)-課程22:無限の力を持つ方法;2. 11. 再帰Vs反復−カリキュラム22:無限の力をどのように持つか−『コンピュータ科学導論』−優達学城.
回文サブストリング
マイコード:
def h2(text):
        text = text.lower()
        for i in range(len(text)):
                for j in range(i+1, len(text)-i-1):
                        if text[i:j] != text[i:j:-1]:
                                continue
                        else:
                                return (i, j)
print h2('racecar')
print h2('Racecar')
print h2('Racecarr')
print h2('Race carr')
print h2('something rac e car going')
print h2('xxxxx')
print h2('Mad am I ma dam.')

私のコードは、1つの長い文字列のうち、左から右の各サブ文字列が、返信文字列であるかどうかを検出するという考えに基づいています.例えば、「racecar」について、r、ra、rac、race......、可能なすべてのサブ文字列が検出されるまで、第2ラウンドはa、ac、ace、acecなどを検出する.
しかし、私のコードは、テストに合格しません.
Peterの元のコードは私が簡単に調整した後:
def longest_subpalindrome_slice(text):
    "Return (i,j) such that text[i:j] is the longest palindrome in text."

    if text == '':
        return (0,0)

    def length(slice):
        a,b = slice
        return b-a

    candidates = [grow(text, start, end)
                    for start in range(len(text))
                    for end in (start, start+1)]

    return max(candidates, key=length)

def grow(text, start, end):
    "Start with a 0- or 1- length palindrome; try to grow a bigger one."

    while (start > 0 and end < len(text)
            and text[start-1].upper() == text[end].upper()):
        start -= 1
        end += 1

    return (start, end)

Peterの元のコード:
def longest_subpalindrome_slice(text):
    "Return (i,j) such that text[i:j] is the longest palindrome in text."
    if text == '': return (0,0)
    def length(slice): a,b = slice; return b-a
    candidates = [grow(text, start, end)
                  for start in range(len(text))
                  for end in (start, start+1)]
    return max(candidates, key=length)

def grow(text, start, end):
    "Start with a 0- or 1- length palindrome; try to grow a bigger one."
    while (start > 0 and end < len(text)
           and text[start-1].upper() == text[end].upper()):
        start -= 1; end += 1
    return (start, end)

def test():
    L = longest_subpalindrome_slice
    assert L('racecar') == L('Racecar') == L('RacecarX') == (0, 7)

参考文献:1.https://blog.csdn.net/qq_33528613/article/details/79431135.