Варе подарили на День Рождения браслет, на котором по кругу записаны строчные буквы латинского алфавита. Изучив внимательно браслет, Варя поняла, что на нём указано какое‑то слово тарабарского языка, состоящее из N букв. Особенность слов тарабарского языка в том, что в них всегда от одной до восьми букв «a».
Подумав, Варя решила, что ей нужен не браслет, а цепочка, и захотела разрезать браслет ровно в одном месте, чтобы получившееся слово было палиндромом. Помогите Варе подсчитать количество способов разрезать браслет так, чтобы получилось слово‑палиндром. Определите позиции возможных разрезов — номера букв, после которых можно разделить браслет (буквы в слове пронумерованы от 1 до N).
Браслет из первого теста
Для справки: палиндром — слово, одинаково читающееся в обоих направлениях, например, «abba».
Формат входных данных
Первая строка содержит целое число N (1≤N≤2⋅106) — длину слова на тарабарском языке.
Вторая строка содержит последовательность из N строчных букв латинского алфавита — слово на тарабарском языке.
Формат выходных данных
В первой строке выведите целое число K — количество способов разрезать браслет.
В следующих K строках выведите позиции возможных разрезов. Выводить позиции разрешено в любом порядке.
Пояснение
В первом тесте разрезать браслет можно двумя способами. Можно сделать разрез между буквами b, тогда получится палиндром «baab», либо между буквами a, тогда получится палиндром «abba».
В втором тесте нельзя разрезать браслет так, чтобы получился палиндром.
Ввод
Вывод
1 Ответ
Ответ:
Сначала надо проверить является ли вообще введённая последовательность палиндромом
for i := 1 to len div 2 do
if s[i] <> s[len-i+1] then begin
f := False;
break;
end;
if f = True then
if (i = Len) or (S[i + 1] in D) then begin… ;проверяем, можно ли разбить на отдельные палиндромы
if Cnt > 1 then Write… ; выписываем количество вариантов
else
writeln(‘0’);
def main():
MOD1 = 1023693581
MOD2 = 1000000009
base = 53
degrees = [0] * int(6e6 + 5)
def initer_all_degrees_for_calculate(start=(1, 1)):
degrees[0] = start
cur = start
for i in range(1, int(6e6 + 2)):
degrees[i] = [degrees[i- 1][0] * base % MOD1, degrees[i- 1][1] * base % MOD2]
return degrees
def Hash(s):
line = []
rs = tuple([0, 0])
for i in range(len(s)):
c = ord(s[i]) — ord(‘a’) + 3
rs = list(rs)
rs[0] = rs[0] * base
rs[0] = (rs[0] + c) % MOD1
rs[1] = rs[1] * base
rs[1] = (rs[1] + c) % MOD2
line.append(tuple(rs))
return line
def Substr(line, l, r):
if l == 0:
return line[r]
deg = r — l + 1
x = line[l — 1]
x = list(x)
x[0] = x[0] * degrees[deg][0] % MOD1
x[1] = x[1] * degrees[deg][1] % MOD2
x = tuple(x)
rs = line[r][0] — x[0], line[r][1] — x[1]
if max(rs[0], rs[1]) < 0:
rs[0] += MOD1
rs[1] += MOD2
elif min(rs[0], rs[1]) < 0:
if rs[0] < 0:
rs[0] += MOD1
else:
rs[1] += MOD2
return tuple(rs)
n = int(input())
sc = input().rstrip(‘\n’)
print(n, sc)
initer_all_degrees_for_calculate()
n3 = n * 3
sc = sc + sc + sc
ans = []
h1 = Hash(sc)
sc = ».join(reversed(sc))
h2 = Hash(sc)
if (n % 2 == 1):
for center in range(n, 2 * n):
l = center — n // 2
r = center + n // 2
x1 = Substr(h1, l, r)
x2 = Substr(h2, n3 — r — 1, n3 — l — 1)
if (x1 == x2):
ans.append(l)
elif (n % 2 == 0):
center1 = n + 1
for center2 in range(n, 2 * n):
l = center1 — n // 2
r = center2 + n // 2
x1 = Substr(h1, l, r)
x2 = Substr(h2, n3 — r — 1, n3 — l — 1)
center1 += 1
if (x1 == x2):
ans.append(l)
print(len(ans))
ans = list(reversed(ans[:]))
for i in range(len(ans)):
ans[i] %= n
if (ans[i] == 0):
ans[i] += n
print(ans[i])
main()