Comprehensive Analysis of Strings in C++: From Basics to Advanced

Click the blue text to follow us

Introduction

In competitions like CSP and NOIP, string manipulation is one of the frequently tested topics. Choosing the right string type, understanding their storage principles, and efficiently manipulating strings often determine whether you can write concise, correct, and efficient code. Today, we will comprehensively review strings in C++, combining code and real competition questions to clarify doubts.

1. What is a String?

1. C-style Strings: Character Arrays

The traditional way inherited from C is the character array, typically defined as follows:

char str[] = "Hello";

The memory layout is as follows:

| ‘H’ | ‘e’ | ‘l’ | ‘l’ | ‘o’ | ‘\0’ |

Note: The final \0 is the termination character. This means you need to consider this character when manipulating, or you may easily encounter array out of bounds errors.

Advantages:

• Occupies less memory and has higher performance.

• Suitable for fixed-length, unmodifiable strings.

Disadvantages:

• Length must be managed manually.

• Lacks flexibility and rich operation functions.

✦

•

✦

2. C++ Standard Library String: std::string

The C++ standard library provides a more modern string type:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s = "Hello";
    s += ", World!";  // Concatenate strings
    cout << s << endl;
}

Advantages:

• Automatically manages memory, avoiding most out-of-bounds issues.

• Supports dynamic expansion.

• Provides rich member functions: size(), substr(), find(), replace(), etc.

Disadvantages:

• Has some performance overhead (dynamic memory allocation, copying).

✦

•

✦

3. Lightweight String View:

std::string_view (C++17)

#include <iostream>
#include <string_view>
using namespace std;
int main() {
    string s = "Hello, World!";
    string_view sv(s);
    cout << sv.substr(0, 5) << endl; // Outputs Hello
}

Characteristics:

• Does not store data, only saves “pointer + length”.

• Efficient, does not copy, very suitable for use in function parameter passing.

• But note: it does not own the data, and its lifecycle depends on the original string.

2. Memory Layout of Strings

Understanding memory layout helps avoid common errors.

Character Arrays

• Fixed memory space, ending with \0.

• Length is determined at declaration, high risk of out-of-bounds.

std::string

• Internally usually contains: character array pointer, length, capacity.

• When expanding, it reallocates larger memory to reduce the overhead of frequent allocations.

std::string_view

• Only contains: pointer + length.

• Does not copy, does not manage memory, efficient but requires caution.

3. Input and Output: Practical Code

1. Character Array Input and Output

#include <iostream>
using namespace std;
int main() {
    char str[50];
    cout << "Please enter a string: ";
    cin.getline(str, 50);
    cout << "You entered: " << str << endl;
}

⚠️ Note: The array size must be sufficient, otherwise input will be truncated.

✦

•

✦

2. std::string Input and Output

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cout << "Please enter a string: ";
    getline(cin, s);
    cout << "You entered: " << s << endl;
}

Safer and more flexible, recommended for use in competitions.

4. Typical Competition Problem Examples?

Example Problem: String concatenation and reversal (adapted from CSP real questions)

Problem: Input two strings, output the concatenated result, and output the reversed string.

Reference Code:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    string c = a + b;
    cout << "Concatenation result: " << c << endl;
    reverse(c.begin(), c.end());
    cout << "Reversed result: " << c << endl;
}

Key Points:

• Master string concatenation +

• Familiar with the reverse() algorithm

• Flexibly use cin and getline for input and output

✦

•

✦

Example Problem: Count the occurrences of letters

Problem: Input a line of string and count the occurrences of each letter.

Thought Process:

• Use an array or map for counting.

• Consider case sensitivity.

Reference Code:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    int cnt[26] = {0};
    for (char ch : s) {
        if (isalpha(ch)) {
            cnt[tolower(ch) - 'a']++;
        }
    }
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > 0) {
            cout << char('a' + i) << ": " << cnt[i] << endl;
        }
    }
}

Key Points:

• Traverse the string.

• ASCII encoding and array mapping.

📚 String Practice Problem List

（CSP & NOIP Past Questions）

1. Basic Problems (Master Input/Output and Basic Operations)

1. String Input and Output

Problem Description:

• Input a line of string and output it.

• Use cin and getline to illustrate the difference.

Solution Thought Process:

• cin >> str can only read the first word (stopping at spaces), so for multi-word strings containing spaces, use getline(cin, str) to read the entire line.

• getline() is not limited by spaces and can read the entire line of text.

Example Code:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cout << "Please enter a string: ";
    getline(cin, s);  // Use getline() to read the entire line
    cout << "You entered: " << s << endl;
}

Key Points:

• The difference between cin and getline.

• How to handle string input containing spaces.

2. Count the occurrences of letters

Problem Description:

• Input a string and count the occurrences of each letter (case insensitive).

Solution Thought Process:

• Traverse the string, counting when encountering letters. Note that case sensitivity is ignored, so use tolower() to convert to lowercase for comparison.

• Use an array or hash table (map) to save the occurrence count of each letter.

Example Code:

#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main() {
    string s;
    getline(cin, s);  // Read the string
    int cnt[26] = {0};  // Used to count letter occurrences (case insensitive)
    for (char ch : s) {
        if (isalpha(ch)) {
            cnt[tolower(ch) - 'a']++;  // Convert character to lowercase and count
        }
    }
    // Output each letter's occurrence count
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > 0) {
            cout << char('a' + i) << ": " << cnt[i] << endl;
        }
    }
}

Key Points:

• String traversal.

• Character case conversion.

• Array counting method.

3. NOIP 2008 Popular Group – ISBN Number

Problem Description:

• Input an ISBN number and check if the check digit is correct.

Solution Thought Process:

• The ISBN number consists of 10 digits, where the last digit is the check digit.

• The check formula is: check digit = 10 – (sum % 11), where sum is the weighted sum of the first 9 digits with their positions.

Example Code:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string isbn;
    cin >> isbn;  // Input ISBN string
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        sum += (isbn[i] - '0') * (10 - i);  // Calculate weighted sum
    }
    int check_digit = (11 - (sum % 11)) % 11;  // Check digit
    int last_digit = (isbn[9] == 'X') ? 10 : (isbn[9] - '0');  // Check the last digit
    if (check_digit == last_digit) {
        cout << "Valid ISBN" << endl;
    } else {
        cout << "Invalid ISBN" << endl;
    }
}

Key Points:

• String and number conversion.

• Check digit calculation.

• Loops and conditional statements.

2. Advanced Problems (Common Competition Problem Types)

1. CSP-J 2019 Second Problem – Sequence Segmentation

Problem Description:

• Given an integer sequence, count how many segments of consecutive identical numbers are in the sequence.

Solution Thought Process:

• Traverse the string, when the current number is different from the previous number, it indicates a new segment has appeared, increment the counter.

Example Code:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int segments = 1;  // At least one segment
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i-1]) {
            segments++;
        }
    }
    cout << segments << endl;
}

Key Points:

• Array traversal.

• Count the number of segments of consecutive identical elements.

2. NOIP 2014 Popular Group – Class Ranking

Problem Description:

• Input multiple names and output them sorted in lexicographical order.

Solution Thought Process:

• Use the sort() function to sort the string array, with the sorting rule being lexicographical order.

Example Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<string> names(n);
    for (int i = 0; i < n; i++) {
        cin >> names[i];
    }
    sort(names.begin(), names.end());  // Sort in lexicographical order
    for (const string & name : names) {
        cout << name << endl;
    }
}

Key Points:

• Use of the sort function.

• Comparison of strings.

3. NOIP 2013 Advanced Group – Counting Problem

Problem Description:

• Given a string, count the occurrences of a specific digit.

Solution Thought Process:

• Traverse the string, directly counting the occurrences of the target digit.

Example Code:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    char digit;
    cin >> s >> digit;
    int count = 0;
    for (char ch : s) {
        if (ch == digit) {
            count++;
        }
    }
    cout << "Digit " << digit << " appeared " << count << " times" << endl;
}

Key Points:

• String traversal and character counting.

4. CSP-S 2020 First Problem – Substring Value Sum

Problem Description:

• For all substrings of a string, calculate their “value” (the number of different characters) sum.

Solution Thought Process:

• Enumerate all substrings, for each substring, calculate the number of different characters. You can use a hash set to calculate the different characters in the substring.

Example Code:

#include <iostream>
#include <set>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int total_value = 0;
    for (int i = 0; i < s.size(); i++) {
        set<char> unique_chars;
        for (int j = i; j < s.size(); j++) {
            unique_chars.insert(s[j]);  // Insert character into set, automatically deduplicate
            total_value += unique_chars.size();  // Calculate the number of different characters
        }
    }
    cout << total_value << endl;
}

Key Points:

• Substring enumeration.

• Using a set to deduplicate and count different characters.

3. Improvement Problems (Combination of Comprehensive and Algorithm)

1. NOIP 2016 Popular Group – Palindrome Date

Problem Description:

• Given a date, find the next palindrome date.

Solution Thought Process:

• The date can be represented as a six-digit number, for example, 20160102. It needs to check if this six-digit number is a palindrome; if not, increment the date until the next palindrome date is found.

Example Code:

#include <iostream>
#include <string>
using namespace std;
bool is_palindrome(const string &s) {
    int n = s.size();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            return false;
        }
    }
    return true;
}
int main() {
    string date;
    cin >> date;
    while (true) {
        // Increment date (ignoring date validity checks)
        int day = stoi(date.substr(6, 2));
        int month = stoi(date.substr(4, 2));
        int year = stoi(date.substr(0, 4));
        // Simple increment date and check palindrome
        day++;
        if (day > 31) {
            day = 1;
            month++;
            if (month > 12) {
                month = 1;
                year++;
            }
        }
        date = to_string(year) + (month < 10 ? "0" : "") + to_string(month) + (day < 10 ? "0" : "") + to_string(day);
        if (is_palindrome(date)) {
            break;
        }
    }
    cout << date << endl;
}

Key Points:

• Date handling.

• Palindrome checking.

2. NOIP 2015 Advanced Group – Information Transmission

Problem Description:

• Task: Information transmission between students, find the shortest cycle.

Solution Thought Process:

• The core of this problem is to transform it into a graph’s shortest cycle problem. Each student can be seen as a node in the graph, and the information transmission relationship can be represented by directed edges.

• The problem can be transformed into finding the smallest cycle in the graph, that is, starting from a certain node, passing through several nodes, and finally returning to the starting point with the shortest path.

• Common algorithms for solving this problem include Floyd-Warshall or BFS/DFS, depending on the specific problem data scale, choose the appropriate algorithm.

Solution:

• First, model the relationships between students as a graph’s adjacency matrix.

• Then use the Floyd-Warshall algorithm or BFS to find the shortest path between each student.

• Finally, calculate the shortest cycle starting from any node.

Example Code

（Based on Floyd-Warshall algorithm）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;  // Infinity, used to initialize distances
int main() {
    int n, m;
    cin >> n >> m;  // n is the number of students, m is the number of information transmission relationships
    // Create adjacency matrix and initialize
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;  // Distance from self to self is 0
    }
    // Read in information transmission relationships
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dist[u-1][v-1] = 1;  // Record the transmission relationship from student u to student v
    }
    // Use Floyd-Warshall algorithm to calculate the shortest path between all students
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // Find the shortest cycle
    int shortest_cycle = INF;
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < shortest_cycle) {
            shortest_cycle = dist[i][i];
        }
    }
    cout << (shortest_cycle == INF ? -1 : shortest_cycle) << endl;  // Output the shortest cycle length
    return 0;
}

Key Points:

• Graph modeling and shortest path calculation.

• Application of the Floyd-Warshall algorithm.

• Finding the shortest cycle problem.

3. Classic Exercise – KMP String Matching

Problem Description:

• Task: Implement the KMP algorithm to find the positions where the pattern string appears in the main string.

Solution Thought Process:

• KMP algorithm is an efficient string matching algorithm that avoids redundant comparisons by utilizing the information already present in the pattern string, thus speeding up the matching process.

• The core of the KMP algorithm is the partial match table (next array), which records the maximum matching length of the prefix and suffix of the pattern string, using this information to skip unnecessary matches.

KMP Algorithm Steps:

1. Preprocess the pattern string to generate the next array.

2. Use the next array to optimize the main string matching process

Example Code:

#include <iostream>
#include <vector>
using namespace std;
// Calculate the next array of the pattern string
void computeNextArray(const string &pattern, vector<int> &next) {
    int m = pattern.length();
    next[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++) {
        while (j >= 0 && pattern[j + 1] != pattern[i]) {
            j = next[j];
        }
        if (pattern[j + 1] == pattern[i]) {
            j++;
        }
        next[i] = j;
    }
}
// Use KMP algorithm to find the pattern string
int KMPSearch(const string &text, const string &pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> next(m);
    computeNextArray(pattern, next);
    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == m) {
                return i - m;  // Match successful, return match position
            }
        } else if (j > 0) {
            j = next[j - 1];  // Use next array to skip unnecessary matches
        } else {
            i++;
        }
    }
    return -1;  // No match found
}
int main() {
    string text, pattern;
    cin >> text >> pattern;
    int result = KMPSearch(text, pattern);
    if (result != -1) {
        cout << "Match position: " << result << endl;
    } else {
        cout << "No match found" << endl;
    }
    return 0;
}

Key Points:

• KMP algorithm: an efficient string matching algorithm.

• Using the next array to skip unnecessary comparisons.

4. CSP-S 2021 Second Problem – Advanced Parenthesis Sequence Matching

Problem Description:

• Task: Based on basic parenthesis matching, add score calculation.

Solution Thought Process:

• This problem requires adding scores for each pair of matching parentheses based on the basic parenthesis matching. A stack can be used to complete the parenthesis matching while scoring each pair of matching parentheses.

• If it is a valid parenthesis sequence, the stack should be empty at the end, and the corresponding total score should be output.

Example Code:

#include <iostream>
#include <stack>
using namespace std;
int main() {
    string s;
    cin >> s;
    stack<int> stk;
    int total_score = 0;
    for (char c : s) {
        if (c == '(') {
            stk.push(0);  // Push to stack for opening parenthesis
        } else if (c == ')') {
            if (stk.empty() || stk.top() == -1) {
                cout << "Invalid" << endl;
                return 0;
            }
            stk.pop();  // Match successful, pop from stack
            total_score += 1;  // Increase score
        }
    }
    if (!stk.empty()) {
        cout << "Invalid" << endl;
    } else {
        cout << "Valid, total score: " << total_score << endl;
    }
    return 0;
}

Key Points:

• Use of stack structure.

• Advanced application of parenthesis matching, combined with score calculation.

Summary and Preparation Suggestions

1

Selection Suggestions:

• Character arrays: suitable for handling simple, fixed-length strings.

• std::string: recommended for daily use, especially for dynamic operations.

• std::string_view: use when performance is sensitive and copying needs to be avoided.

2

Common Pitfalls:

• Forgetting to add \0 for C-style strings.

• Mixing cin >> and getline() causing newline issues.

• std::string_view pointing to destroyed temporary objects.

3

Competition Response:

• std::string is sufficient for most CSP and NOIP problems.

• In special cases (large input, high performance requirements), consider string_view or character arrays.

Mastering various representations and manipulation techniques of strings will help you write more efficient and robust code in competitions.

👉 For those preparing for competitions, practice more problems related to strings, especially searching, matching, and counting types of problems, which are often high-frequency points in CSP and NOIP.

END

Like

Collect

Share

Explore the forefront of educational technology, empowering future learning capabilities!

“Bit Island Education Technology” is committed to using innovative technology to create a more efficient, interesting, and future-oriented learning experience.

• Get the latest educational technology products and course materials

• Learn practical and efficient learning methods and educational concepts

• Understand innovative teaching tools and classroom application cases

• Participate in exclusive activities and win learning benefits

Scan the code to follow us and start your journey in smart education! 👇

BIT ISLAND

Long press to scan

WeChat ID丨bit_island_Terry

WeChat Search丨Bit Island Education Technology