Задача 6056. Источник: Поляков. Задание КИМ 24

Страница задачи 6056

Решение

Данную задачу нельзя решать полным перебором всех возможных строк, т.к. такое решение будет работать слишком долго даже на компилируемых языках. Эффективным решением является анализ строк из середины. Строка-палиндром может иметь нечетную и четную длину. Если длина нечетная, то в середине один символ, если длина четная - в середине два одинаковых символа, а справа и слева от середины зеркально одинаковые цепочки. Пройдем по всем символам строки и парам символов, расценивая их, как середину, и найдем ответ на задачу.

Python

s = open('24-241.txt').readline()
mx = 0
for i in range(len(s)):
    j = 1
    while i - j >= 0 and i + j < len(s)  and s[i - j] == s[i + j]:
        mx = max(mx, j * 2 + 1)
        j += 1
    if i < len(s) - 1 and s[i] == s[i + 1]:
        j = 1
        while i - j >= 0 and i + j + 1 < len(s)  and s[i - j] == s[i + j + 1]:
            mx = max(mx, j * 2 + 2)
            j += 1
print(mx)

PascalABC

var
    i, j, max: Integer;
    s: String;
    f: TEXT;
begin
    Assign(f, '24-241.txt');
    Reset(f);
    Readln(f, s);
    max := 0;
    for i := 1 to s.Length do
    begin
        j := 1;
        while (i - j > 0) and (i + j <= s.Length) and (s[i - j] = s[i + j]) do
        begin
            if max < j * 2 + 1 then
                max := j * 2 + 1;
            j := j + 1;
        end;
        if (i < s.Length) and (s[i] = s[i + 1]) then
        begin
            j := 1;
            while (i - j > 0) and (i + j + 1 <= s.Length) and (s[i - j] = s[i + j + 1]) do
            begin
                if max < j * 2 + 2 then
                    max := j * 2 + 2;
                j := j + 1;
            end;
        end;
    end;
    Writeln(max);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("24-241.txt");
    string s;
    f >> s;
    int max = 0;
    for (int i = 0; i < s.length(); i++)
    {
        int j = 1;
        while (i - j >= 0 && i + j < s.length() && s[i - j] == s[i + j])
        {
            if (max < j * 2 + 1)
                max = j * 2 + 1;
            j++;
        }
        if (i < s.length() - 1 && s[i] == s[i + 1])
        {
            j = 1;
            while (i - j >= 0 && i + j + 1 < s.length() && s[i - j] == s[i + j + 1])
            {
                if (max < j * 2 + 2)
                    max = j * 2 + 2;
                j++;
            }
        }
    }
    cout << max << endl;
}

Ответ

19

Отправить замечание по решению