Solução por Lúcio Cardoso
Para checar se uma string $$S$$ qualquer é um palíndromo, basta checar se o caractere de cada posição $$i$$ em $$S$$ é igual ao caractere na mesma posição $$i$$ da string reversa de $$S$$. Logo, é possível realizar a checagem em $$O(N)$$, onde $$N$$ é o tamanho da string.
Pela definição do problema, queremos encontrar a maior substring (string formada por posições consecutivas da palavra original) que é um palíndromo. Podemos então checar todas as $$O(n^2)$$ substrings com o algoritmo descrito acima em $$O(n)$$, atualizando a maior resposta caso a substring seja um palíndromo. A complexidade final será então $$O(n^3)$$.
Confira o código abaixo para melhor entendimento:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Noic – Iniciante – Semana 51 – Problema 1 | |
| // Complexidade: O(n^3) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| string s; | |
| bool check(int a, int b) | |
| { | |
| // substring de [a..b] e sua reversa | |
| string S, R; | |
| for (int i = a; i <= b; i++) | |
| { | |
| S.push_back(s[i]); | |
| R.push_back(s[i]); | |
| } | |
| reverse(R.begin(), R.end()); | |
| for (int i = 0; i < S.size(); i++) | |
| if (S[i] != R[i]) | |
| return false; | |
| return true; | |
| } | |
| int main(void) | |
| { | |
| cin >> s; | |
| int ans = 0; | |
| for (int i = 0; i < s.size(); i++) | |
| { | |
| for (int j = i; j < s.size(); j++) | |
| { | |
| if (check(i, j)) | |
| { | |
| // se a substring [i..j] for um palíndromo, | |
| // atualizamos nossa resposta | |
| ans = max(ans, j-i+1); | |
| } | |
| } | |
| } | |
| cout << ans << "\n"; | |
| } |
Comente