Strings

How strings are stored and compared, why bytes are not characters, and the main string algorithms — palindromes, anagrams, KMP, Z, rolling hashes, Manacher and tries — with a map of where each is covered in depth.

What you will learn

Prerequisites: Modules 4–5.

Concepts

Character encoding, ASCII versus Unicode, UTF-8 basics, mutable versus immutable strings, substring, pattern matching, lexicographic order, palindrome, anagram, tokenization, and string hashing.

Syntax

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

For production-grade Unicode processing, explain that byte indexing is not the same as character or grapheme indexing. In UTF-8, é takes two bytes, so size() reports 5; reversing the bytes would corrupt it. Some user-visible characters (graphemes such as flags or emoji with modifiers) span several code points as well.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "level";
    reverse(s.begin(), s.end());
    bool palindrome = equal(s.begin(), s.end(), s.rbegin());
    cout << s << " is a palindrome: " << boolalpha << palindrome << '\n';

    string t = "Was it a car or a cat I saw?";
    string letters;
    for (unsigned char c : t) if (isalnum(c)) letters += char(tolower(c));
    int i = 0, j = (int)letters.size() - 1;
    bool ok = true;
    while (i < j) if (letters[i++] != letters[j--]) { ok = false; break; }
    cout << "\"" << t << "\" ignoring case and punctuation: " << ok << '\n';

    string u8 = "caf\xC3\xA9";               // "café" encoded in UTF-8
    cout << "\"café\" has " << u8.size() << " bytes but 4 characters\n";
    cout << "lexicographic: \"apple\" < \"apples\" < \"banana\": " << (string("apple") < "apples" && string("apples") < "banana") << '\n';
}

level is a palindrome: true
"Was it a car or a cat I saw?" ignoring case and punctuation: true
"café" has 5 bytes but 4 characters
lexicographic: "apple" < "apples" < "banana": true

Important algorithms

Naive pattern search.

KMP prefix-function / failure function.

Rabin–Karp rolling hash.

Boyer–Moore overview.

Manacher's algorithm for palindromic substrings.

Trie-based prefix search.

Suffix array, LCP array, suffix automaton, suffix tree overview.

O(n·m) worst case KMP, Z algorithm expected O(n + m) sublinear on typical text, skips using bad-character/good-suffix rules O(L) per word Suffix array + LCP

O(n log n) construction (simple versions) Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The second input is the classic bad case: every alignment matches 99 characters before failing. KMP (Module 43) never re-reads text characters and needs at most about 2n comparisons.

Anagrams by counting The array<int, 26> version assumes lowercase ASCII letters — validate input or use a hash map for general alphabets.

#include <bits/stdc++.h>
using namespace std;

vector<int> naiveSearch(const string& text, const string& pat, long long& comparisons) {
    vector<int> hits;
    for (size_t i = 0; i + pat.size() <= text.size(); ++i) {
        size_t j = 0;
        while (j < pat.size() && (++comparisons, text[i + j] == pat[j])) ++j;
        if (j == pat.size()) hits.push_back((int)i);
    }
    return hits;
}

int main() {
    long long c = 0;
    auto hits = naiveSearch("abracadabra", "abra", c);
    cout << "\"abra\" found at:";
    for (int h : hits) cout << ' ' << h;
    cout << " (" << c << " character comparisons)\n";
    string text(10000, 'a'), pat = string(99, 'a') + "b";
    c = 0;
    naiveSearch(text, pat, c);
    cout << "worst case, n=10000, m=100: " << c << " comparisons (about n*m)\n";
}

"abra" found at: 0 7 (16 character comparisons)
worst case, n=10000, m=100: 990100 comparisons (about n*m)

#include <bits/stdc++.h>
using namespace std;

bool isAnagram(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    array<int, 26> cnt{};
    for (char c : a) ++cnt[c - 'a'];
    for (char c : b) if (--cnt[c - 'a'] < 0) return false;
    return true;
}

int main() {
    cout << boolalpha << isAnagram("listen", "silent") << ' ' << isAnagram("rat", "car") << '\n';
    vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    map<string, vector<string>> groups;                 // key: sorted letters
    for (const string& w : words) { string k = w; sort(k.begin(), k.end()); groups[k].push_back(w); }
    for (const auto& [k, g] : groups) {
        cout << k << ":";
        for (const string& w : g) cout << ' ' << w;
        cout << '\n';
    }
}

true false
abt: bat
aet: eat tea ate
ant: tan nat

Advanced string topics

Minimum edit distance, longest common subsequence, longest common substring, string compression, lexicographically smallest construction, multiple-pattern matching with Aho–Corasick, and hashing collision considerations.

Edit distance and LCS are dynamic programming (Module 22); Aho–Corasick builds a trie of all patterns with failure links so one pass over the text finds every occurrence of every pattern in O(n + total pattern length + matches).

Practice

Easy: check whether one string is a rotation of another (hint: search in a + a).

Medium: longest substring without repeating characters (Module 24).

Hard: shortest palindrome by adding characters in front (hint: prefix function of s + "#" + reverse(s)).

Quiz

? Why did `"café"` report a size of 5?
+ `size()` counts bytes, and UTF-8 encodes é in two bytes. :: Byte indexing is not character indexing.
- C++ counts the terminating NUL. :: std::string::size excludes it.
- é is two characters. :: It is one character (one code point here).
- A bug in the compiler. :: No.

? The naive search made 990,100 comparisons on n = 10000, m = 100. What is its worst-case complexity?
+ O(n·m) :: Each of about n alignments can compare up to m characters.
- O(n + m) :: That is KMP or Z.
- O(n log m) :: No.
- O(m²) :: No.

? Which are valid anagram checks for lowercase ASCII words? (select all that apply)
+ Compare 26 letter counts :: O(n).
+ Sort both words and compare :: O(n log n).
- Compare lengths only :: Necessary, not sufficient.
- Compare the sums of character codes :: "ad" and "bc" have equal sums.