Я решаю проблему, которая имеет некоторые ограничения по времени и памяти, и, к сожалению, это не соответствует ограничениям по времени.
Я довольно новичок в Python, поэтому любые отзывы о более быстрых / лучших методах приветствуются.
Вот проблема, которую пытается решить программа:
Определите сходство двух строк A & B как длину самого длинного общего префикса, который они разделяют.т.е. сходство AAAB и AABCAAAB равно 2.
Программа должна вывести сумму сходств входной строки со всеми ее суффиксами.то есть для AAAB, он должен вывести
сходство (AAAB, AAAB) + сходство (AAAB, AAB) + сходство (AAAB, AB) + сходство (AAAB, B) = 4 + 2 + 1 + 0 = 7
Первая строка ввода - это количество строк, которые нужно ввести, и каждая последующая строка содержит строку для обработки.
from array import array
n = int(sys.stdin.readline())
A = [0] * n #List of answers
for i in range(1,n+1):
string = sys.stdin.readline().strip()
A[i-1] = len(string)
for j in range(1, len(string)):
substr = string[j:len(string)]
sum = 0
for k in range(0, len(substr)):
if substr[k] != string[k]:
break
else:
sum += 1
A[i-1] += sum
for i,d in enumerate(A):
print d