9. DSA with C++ - String Algorithms

String Algorithms

String Reversal Algorithm

The string reversal algorithm involves reversing the characters in a string to create a reversed version of the original string. Here's an example implementation:

#include <iostream>
#include <algorithm> // for std::reverse
int main() {
    std::string str = "Hello, World!";
    // Step 1: Convert the string to a character array
    char* charArray = new char[str.length() + 1];
    strcpy(charArray, str.c_str());
    // Step 2: Reverse the character array
    std::reverse(charArray, charArray + str.length());
    // Step 3: Convert the reversed character array back to a string
    std::string reversedStr(charArray);
    // Step 4: Display the reversed string
    std::cout << "Original string: " << str << std::endl;
    std::cout << "Reversed string: " << reversedStr << std::endl;
    // Step 5: Clean up memory
    delete[] charArray;
    return 0;
}
            

String Palindrome Algorithm

The string palindrome algorithm checks whether a given string is a palindrome, meaning it reads the same forwards and backwards. Here's an example implementation:

#include <iostream>
#include <algorithm> // for std::reverse
bool isPalindrome(const std::string& str) {
    std::string reversedStr = str;
    std::reverse(reversedStr.begin(), reversedStr.end());
    return (str == reversedStr);
}
int main() {
    std::string str = "madam";
    // Check if the string is a palindrome
    bool isPal = isPalindrome(str);
    // Display the result
    std::cout << "String: " << str << std::endl;
    if (isPal) {
        std::cout << "It is a palindrome." << std::endl;
    } else {
        std::cout << "It is not a palindrome." << std::endl;
    }
    return 0;
}
            

String Anagram Algorithm

The string anagram algorithm checks whether two given strings are anagrams, meaning they contain the same characters, but possibly in a different order. Here's an example implementation:

#include <iostream>
#include <algorithm> // for std::sort
bool isAnagram(const std::string& str1, const std::string& str2) {
    std::string sortedStr1 = str1;
    std::string sortedStr2 = str2;
    // Sort the characters in both strings
    std::sort(sortedStr1.begin(), sortedStr1.end());
    std::sort(sortedStr2.begin(), sortedStr2.end());
    return (sortedStr1 == sortedStr2);
}
int main() {
    std::string str1 = "listen";
    std::string str2 = "silent";
    // Check if the strings are anagrams
    bool isAna = isAnagram(str1, str2);
    // Display the result
    std::cout << "String 1: " << str1 << std::endl;
    std::cout << "String 2: " << str2 << std::endl;
    if (isAna) {
        std::cout << "They are anagrams." << std::endl;
    } else {
        std::cout << "They are not anagrams." << std::endl;
    }
    return 0;
}
            

String Pattern Matching (KMP Algorithm)

The Knuth-Morris-Pratt (KMP) algorithm efficiently finds occurrences of a pattern within a given string. It utilizes a preprocessed table to avoid unnecessary character comparisons. Here's an example implementation:

#include <iostream>
#include <vector>
// Function to preprocess the pattern and generate the failure table
std::vector<int> computeFailureTable(const std::string& pattern) {
    int patternLength = pattern.length();
    std::vector<int> failureTable(patternLength, 0);
    int j = 0;
    for (int i = 1; i < patternLength; i++) {
        if (pattern[i] == pattern[j]) {
            failureTable[i] = j + 1;
            j++;
        } else {
            if (j != 0) {
                j = failureTable[j - 1];
                i--;
            } else {
                failureTable[i] = 0;
            }
        }
    }
    return failureTable;
}
// Function to perform string pattern matching using the KMP algorithm
std::vector<int> patternMatching(const std::string& text, const std::string& pattern) {
    int textLength = text.length();
    int patternLength = pattern.length();
    std::vector<int> matches;
    std::vector<int> failureTable = computeFailureTable(pattern);
    int i = 0, j = 0;
    while (i < textLength) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == patternLength) {
                matches.push_back(i - j);
                j = failureTable[j - 1];
            }
        } else {
            if (j != 0) {
                j = failureTable[j - 1];
            } else {
                i++;
            }
        }
    }
    return matches;
}
int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    // Find all occurrences of the pattern in the text
    std::vector<int> matches = patternMatching(text, pattern);
    // Display the matches
    std::cout << "Pattern: " << pattern << std::endl;
    std::cout << "Matches found at indices: ";
    for (int i = 0; i < matches.size(); i++) {
        std::cout << matches[i];
        if (i != matches.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << std::endl;
    return 0;
}