Как личное упражнение, вот вам (надеюсь) хорошо прокомментированный код с некоторыми подсказками.
#!/usr/bin/env python2
# Let's take this string:
a = "palindnilddafa"
# I surround with a try/catch block, explanation following
try:
# In this loop I go from length of a minus 1 to 0.
# range can take 3 params: start, end, increment
# This way I start from the thow longest subsring,
# the one without the first char and without the last
# and go on this way
for i in range(len(a)-1, 0, -1):
# In this loop I want to know how many
# Palidnrome of i length I can do, that
# is len(a) - i, and I take all
# I start from the end to find the largest first
for j in range(len(a) - i):
# this is a little triky.
# string[start:end] is the slice operator
# as string are like arrays (but unmutable).
# So I take from j to j+i, all the offsets
# The result of "foo"[1:3] is "oo", to be clear.
# with string[::-1] you take all elements but in the
# reverse order
# The check string1 in string2 checks if string1 is a
# substring of string2
if a[j:j+i][::-1] in a:
# If it is I cannot break, 'couse I'll go on on the first
# cycle, so I rise an exception passing as argument the substring
# found
raise Exception(a[j:j+i][::-1])
# And then I catch the exception, carrying the message
# Which is the palindrome, and I print some info
except Exception as e:
# You can pass many things comma-separated to print (this is python2!)
print e, "is the longest palindrome of", a
# Or you can use printf formatting style
print "It's %d long and start from %d" % (len(str(e)), a.index(str(e)))
После обсуждения, и мне немного жаль, если это не так. Я написал другую реализацию palindrome-searcher, и если sberry2A может, я хотел бы узнать результаты некоторых тестов производительности!
Имейте в виду, есть много ошибок (я полагаю) об указателях и сложной проблеме "+1 -1", но идея ясна. Начните с середины, а затем расширяйтесь, пока не сможете.
Вот код:
#!/usr/bin/env python2
def check(s, i):
mid = s[i]
j = 1
try:
while s[i-j] == s[i+j]:
j += 1
except:
pass
return s[i-j+1:i+j]
def do_all(a):
pals = []
mlen = 0
for i in range(len(a)/2):
#print "check for", i
left = check(a, len(a)/2 + i)
mlen = max(mlen, len(left))
pals.append(left)
right = check(a, len(a)/2 - i)
mlen = max(mlen, len(right))
pals.append(right)
if mlen > max(2, i*2-1):
return left if len(left) > len(right) else right
string = "palindnilddafa"
print do_all(string)