Largest palindrome in a string? C++

Question

I’m trying to make a code to be able to figure out, for example in phrases like, The blue macaw is beautiful! What’s the big one? in which case the answer would be: macaw I got to the code below but I don’t know how to develop it to get the solution. Can anyone help me? I would like anyone who can help me explain how you came to this logic so I can understand. Thank you.

#include <iostream>

using namespace std;

int main(){

    string frase; // Guarda uma string

    bool ok = true; // Ajuda a verificar se a variável é um palíndrormo


    getline(cin,frase); // Recebe a frase que será tratada.

    int tam = frase.size(); // Atribui na variável tam o tamanho da string: frase.

    for (int i = 0, j = tam - 1 ; i < tam - 1; i++, j--){

        if( frase[i] == frase[j] ){
            ok = true;
        }else{
            ok = false;
        }

    }

        if( ok == true ){
            cout << "E palindromo" <<  endl;
        }else{
            cout << "Nao e palindromo" << endl;
        }

    return 0;
}

Answer 1

The code below searches a sentence for the sequence of characters that form a palindrome, as long as the sentence does not use comma or accent, for this case just include a check every round of the for in the string sub_sentence.

#include <iostream>

using namespace std;

bool check_palindrome(string sentence) {

    string sentence_without_space;

    //Isto é necessário caso queira vê palidromes de várias palavras em uma frase
    for (int i = 0; i < sentence.size(); i++) {

        if (sentence[i] == ' ') {

            continue;
        }

        //Removendo os espaços em branco
        sentence_without_space.push_back(sentence[i]);
    }

    //Verificando se é palindrome
    for (int i = 0, j = sentence_without_space.size() - 1; i <= j; i++, j--) {

        if (sentence_without_space[i] != sentence_without_space[j]) {

            return false;
        }
    }

    return true;
}


string analyze_sentence(string sentence) {

    string greater_palindrome;
    string sub_sentence;
    string sub_sentence_palindrome;
    //---

    //Normaliza a entrada de dados
    for (int i = 0; i < sentence.size(); i++) {

        sentence[i] = tolower(sentence[i]);
    }

    //Percorre toda a sequencia de caracteres da frase, comparando se há um palindrome a partir do caracter atual
    for (int i = 0; i < sentence.size(); i++) {

        //Caso o caracter inicial seja fazio ignora e não verifica
        if (sentence[i] == ' ')
            continue;

        //Selecionando a senquancia de busca atual
        sub_sentence = sentence.substr(i);

        //Percorre do final para o inicio verificando se o conjunto de caracteres entre os indices i e j formam um palindrome
        for (int j = sub_sentence.size(); j > 0; j--) {

            //Caso o caracter final seja fazio ignora e não verifica
            if (sub_sentence[j] == ' ')
                continue;

            //Extrai o possível palindrome
            sub_sentence_palindrome = sub_sentence.substr(0, j);

            //Verifica se é um palindrome
            if (check_palindrome(sub_sentence_palindrome)) {

                //Sendo um palindrome verifica e salva o de maior tamanho
                if (sub_sentence_palindrome.size() > greater_palindrome.size()) {

                    greater_palindrome = sub_sentence_palindrome;
                }
                break; //Aqui você pode encerrar a busca pois este for só irá decrementar o J e procurar por coisa menores ao palindrome atual
            }
        }
    }

    return greater_palindrome;
}

int main() {

    string greater_palindrome = analyze_sentence("Enquanto ele estava seco de raiva coloco no colo caviar e doces!");

    printf("%s\n", greater_palindrome.c_str());

    system("pause");
    return 0;
}

The code is quite commented on I believe it will be easy to understand. In general, I analyze all the sequences of characters from the first index of the sentence and always decreasing the size of the sequence investigated. For example, in the phrase 'The blue macaw is beautiful! 'I start analyzing everything then decreasing the size of the string in 1 and then my search is in the string 'The blue macaw is beautiful', then 'The blue macaw is Lind', and so on. After doing this, me based on the beginning of the string being the first position, I increment the index of beginning of the string and do the search from 'blue macaw is beautiful! ', and I keep decreasing the size of this analysis into 'blue macaw is beautiful'. Whenever a new sequence is formed to be evaluated whether or not it is a palindrome I check the size of the palindrome to save only the largest size.

Note: Mario’s comment on Manacher’s algorithm should be interesting, because it should be something more optimized, I did not read.