Solução Informática Iniciante - Semana 51 - Problema 1

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:

	// 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";
	}

view raw

noic-iniciante-s51-p1.cpp

hosted with ❤ by GitHub