Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. Такой алгоритм будет работать O(|S|^2), что при ограничении |S| <= 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго.
Оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. Их можно найти, а затем увеличивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений.
Однако задачу можно решить и за линейное время. Например, существует алгоритм Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию.
Пример 1: "длинная" подстрока-палиндром: cbbaabbaabbc в которой известна подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром: cbbaabbaabbc Пример 2: "длинная" подстрока палиндром: bbaabbaabbaa Зная, что в ней есть подстрока-палиндром bbaabbaabbaa, можно явные сравнения для подстроки с центром в bbaabbaabbaa начинать уже с bbaabbaabbaa
Если не хочется писать самостоятельно, алгоритм Манакера легко находится.
Логические знаки не дает вставлять - пишу их союзами и частицами подчеркнутыми. 1) Число 376 четное и трехзначное. А = "Число 376 четное" В = "Число 376 трехзначное" А и В 2) Неверно, что Солнце движется вокруг Земли. А = "Солнце движется вокруг Земли" Не А 3) Земля имеет форму шара. А = "Земля имеет форму шара" А 4) На уроке математики старшеклассники отвечали на вопросы учителя и писали самостоятельную работу. А = "На уроке математики старшеклассники отвечали на вопросы учителя" В = "На уроке математики старшеклассники писали самостоятельную работу" А и В 5) Если сумма цифр числа делится на 3, то число делится на 3. А = "Сумма цифр числа делится на 3" В = "Число делится на 3" А стрелка к В 6) Число делится на 3 тогда и только тогда, когда сумма цифр числа делится на 3 А = "Число делится на 3 " В = "Сумма цифр числа делится на 3" А стрелка в обе стороны В
Оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. Их можно найти, а затем увеличивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений.
Однако задачу можно решить и за линейное время. Например, существует алгоритм Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию.
Пример 1: "длинная" подстрока-палиндром:
cbbaabbaabbc
в которой известна подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром:
cbbaabbaabbc
Пример 2: "длинная" подстрока палиндром:
bbaabbaabbaa
Зная, что в ней есть подстрока-палиндром
bbaabbaabbaa,
можно явные сравнения для подстроки с центром в
bbaabbaabbaa
начинать уже с
bbaabbaabbaa
Если не хочется писать самостоятельно, алгоритм Манакера легко находится.
1) Число 376 четное и трехзначное.
А = "Число 376 четное"
В = "Число 376 трехзначное"
А и В
2) Неверно, что Солнце движется вокруг Земли.
А = "Солнце движется вокруг Земли"
Не А
3) Земля имеет форму шара.
А = "Земля имеет форму шара"
А
4) На уроке математики старшеклассники отвечали на вопросы учителя и писали самостоятельную работу.
А = "На уроке математики старшеклассники отвечали на вопросы учителя"
В = "На уроке математики старшеклассники писали самостоятельную работу"
А и В
5) Если сумма цифр числа делится на 3, то число делится на 3.
А = "Сумма цифр числа делится на 3"
В = "Число делится на 3"
А стрелка к В
6) Число делится на 3 тогда и только тогда, когда сумма цифр числа делится на 3
А = "Число делится на 3 "
В = "Сумма цифр числа делится на 3"
А стрелка в обе стороны В