palindrome using KMP algorithm in C++

In this chapter of C++ program, we are going to learn about:

palindrome program in c++ for string using KMP algorithm.

Introduction to Palindrome

Palindromes are fascinating structures in strings that read the same backward as forward. In this article, we explore a simple approach to transform any given string into a palindrome using C++. We'll discuss the concepts of string manipulation, the Longest Prefix Suffix (LPS) algorithm, and how they come together to construct palindromes efficiently.

Understanding the Palindrome Approach

The core idea behind our approach involves:

1. Reversing the String: By reversing the original string, we can identify the longest common prefix and suffix, which helps in determining the additional characters needed to form a palindrome.

2. Using the Longest Prefix Suffix (LPS) Array: This algorithm is pivotal in finding the longest prefix which is also a suffix within a concatenated string of the original and reversed strings.

Implementation of Palindrome

Let's break down the implementation steps:

Reverse Function: We define a function to reverse a given string, which is crucial for constructing the palindrome.
LPS Function: This function computes the LPS array, which aids in determining the longest palindromic suffix.
Make Palindrome Function: Combining the above functions, this function computes the palindrome from the original string along with the characters added to make it a palindrome.

Lets now move towards kmp algorithm in c++ code.

CODE FOR PALINDROME

Palindrome program in c++ for string is given below:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to reverse a string
string reverseString(const string &s) {
    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());
    return rev_s;
}

// Function to compute the LPS array
vector<int> findLPS(const string &s) {
    vector<int> lps(s.size(), 0);
    int length = 0;
    int i = 1;
    
    while (i < s.size()) {
        if (s[i] == s[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// Function to create palindrome and return added characters
string makePalindrome(const string &s) {
    string rev_s = reverseString(s);
    string combined = s + "$" + rev_s;
    vector<int> lps = findLPS(combined);
    
    int chars_to_add = s.size() - lps.back();
    string added_chars = rev_s.substr(0, chars_to_add);
    string palindrome = s + added_chars + s[0];
    
    return palindrome;
}

int main() {
    string s;
    cout << "Enter a string: ";
    cin >> s;
    
    string result = makePalindrome(s);
    cout << "The required palindrome is: " << result << endl;
    
    return 0;
}

OUTPUT

Enter a string: race

The required palindrome is: racecar

You can try to enter another string of your choice and get the possible palindrome constructed for it.

This wraps up our session on palindrome in c++ program.

CPP Programs

Would you like to see your article here on tutorialsinhand. Join Write4Us program by tutorialsinhand.com

About the Author

kumkum tiwari

Page Views : Published Date : Jul 10,2024

Please Share this page