#CSPJCSMN10. 普及组程序专项-字符串

普及组程序专项-字符串

普及组字符串算法专题训练（10题）

题目1：字符串匹配（KMP算法）

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

vector<int> getNext(string pattern) {
    int n = pattern.size();
    vector<int> next(n, 0);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

int kmp(string text, string pattern) {
    int m = text.size(), n = pattern.size();
    if (n == 0) return 0;
    vector<int> next = getNext(pattern);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == n) return i - j;
    return -1;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;
    int pos = kmp(text, pattern);
    if (pos != -1) {
        cout << "Found at position: " << pos << endl;
    } else {
        cout << "Not found" << endl;
    }
    return 0;
}

判断题

  1. KMP算法的时间复杂度是O(m+n)。 ( )
  2. getNext函数计算的是最长公共前后缀长度。 ( )
  3. 当j=-1时，表示需要将模式串从头开始匹配。 ( )

选择题 4. 对于模式串"ABABC"，next数组的值是（ ）。
A. [-1, 0, 0, 1, 2]
B. [-1, 0, 1, 2, 0]
C. [0, 1, 2, 3, 4]
D. [-1, 0, 0, 0, 1]

  1. 如果文本串是"ABABABABC"，模式串是"ABABC"，匹配成功时的起始位置是（ ）。
    A. 0
    B. 2
    C. 4
    D. 6

题目2：字符串分割

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

vector<string> split(string s, char delimiter) {
    vector<string> tokens;
    string token;
    istringstream tokenStream(s);
    while (getline(tokenStream, token, delimiter)) {
        if (!token.empty()) {
            tokens.push_back(token);
        }
    }
    return tokens;
}

int main() {
    string s = "a,b,c,,d";
    vector<string> result = split(s, ',');
    for (string token : result) {
        cout << token << " ";
    }
    return 0;
}

判断题

  1. 这个分割函数会忽略连续的分隔符产生的空字符串。 ( )
  2. 使用istringstream可以方便地实现字符串分割。 ( )
  3. 如果字符串以分隔符结尾，最后一个空字符串会被保留。 ( )

选择题 4. 对于输入字符串"a,b,c,,d"，分割后的token个数是（ ）。
A. 3
B. 4
C. 5
D. 6

  1. 如果希望保留空字符串，应该修改哪部分代码？（ ）
    A. 删除if (!token.empty())判断
    B. 修改getline参数
    C. 使用不同的分割方法
    D. 无法实现

题目3：字符串反转（单词级别）

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

string reverseWords(string s) {
    // 去除前后空格
    int left = 0, right = s.size() - 1;
    while (left <= right && s[left] == ' ') left++;
    while (left <= right && s[right] == ' ') right--;
    
    string result;
    int wordEnd = right;
    while (left <= right) {
        int wordStart = right;
        while (wordStart >= left && s[wordStart] != ' ') wordStart--;
        result += s.substr(wordStart + 1, wordEnd - wordStart);
        if (wordStart >= left) result += ' ';
        right = wordStart - 1;
        wordEnd = right;
    }
    return result;
}

int main() {
    string s = "  hello world  ";
    string result = reverseWords(s);
    cout << "\"" << result << "\"" << endl;
    return 0;
}

判断题

  1. 这个算法将字符串中的单词顺序反转，但每个单词本身的字符顺序不变。 ( )
  2. 算法正确处理了字符串开头和结尾的空格。 ( )
  3. 算法的时间复杂度是O(n)。 ( )

选择题 4. 输入字符串" hello world "，输出是（ ）。
A. "world hello"
B. "olleh dlrow"
C. "dlrow olleh"
D. " world hello "

  1. 这个算法的空间复杂度是（ ）。
    A. O(1)
    B. O(n)
    C. O(n²)
    D. O(log n)

题目4：最长公共前缀

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

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    vector<string> strs = {"flower", "flow", "flight"};
    string result = longestCommonPrefix(strs);
    cout << "Longest common prefix: " << result << endl;
    return 0;
}

判断题

  1. 这个算法通过不断缩短前缀来寻找最长公共前缀。 ( )
  2. 如果输入数组为空，函数返回空字符串。 ( )
  3. 算法中使用了字符串的find函数，它用于查找子串，如果找到返回0。 ( )

选择题 4. 对于输入["flower","flow","flight"]，最长公共前缀是（ ）。
A. "fl"
B. "flow"
C. "flight"
D. "f"

  1. 这个算法的最坏时间复杂度是（ ）。
    A. O(n) // n是字符串数组的长度
    B. O(m) // m是第一个字符串的长度
    C. O(n*m) // n是数组长度，m是字符串平均长度
    D. O(nlogm)

题目5：字符串压缩（连续字符计数）

#include <iostream>
#include <string>
using namespace std;

string compress(string s) {
    if (s.empty()) return s;
    string result;
    int count = 1;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && s[i] == s[i+1]) {
            count++;
        } else {
            result += s[i];
            if (count > 1) {
                result += to_string(count);
            }
            count = 1;
        }
    }
    return result.size() < s.size() ? result : s;
}

int main() {
    string s = "aabcccccaaa";
    string result = compress(s);
    cout << result << endl;
    return 0;
}

判断题

  1. 这个压缩算法将连续相同的字符用字符加上出现次数表示。 ( )
  2. 如果压缩后的字符串比原字符串长，则返回原字符串。 ( )
  3. 对于单个字符，压缩后仍然保留，但不添加计数。 ( )

选择题 4. 输入字符串"aabcccccaaa"压缩后的结果是（ ）。
A. "a2bc5a3"
B. "a2b1c5a3"
C. "a2bc5a3"
D. "a2b1c5a3"

  1. 这个算法的时间复杂度是（ ）。
    A. O(n)
    B. O(n²)
    C. O(nlogn)
    D. O(1)

题目6：字符串转整数（atoi）- 程序填空

#include <iostream>
#include <string>
#include <climits>
using namespace std;

int myAtoi(string s) {
    int i = 0;
    int sign = 1;
    long long result = 0;
    
    // 跳过前导空格
    while (i < s.size() && s[i] == ' ') {
        i++;
    }
    
    // 处理正负号
    if (i < s.size() && (s[i] == '+' || s[i] == '-')) {
        sign = (s[i] == '+') ? 1 : -1;
        i++;
    }
    
    // 转换数字
    while (i < s.size() && isdigit(s[i])) {
        result = result * 10 + (s[i] - '0');
        // 检查溢出
        if (result * sign > INT_MAX) {
            return INT_MAX;
        }
        if (result * sign < INT_MIN) {
            return INT_MIN;
        }
        i++;
    }
    
    return result * sign;
}

选择题（选择正确的代码填入空白处）

  1. 在转换数字部分，空白处的代码应该是（ ）。
    A. result = result * 10 + (s[i] - '0');
    B. result = result + (s[i] - '0');
    C. result = result * 10 + s[i];
    D. result = result * 10 + (s[i] + '0');

  2. 检查溢出的代码中，空白处应该是（ ）。
    A. if (result > INT_MAX)
    B. if (result * sign > INT_MAX)
    C. if (result > INT_MAX && sign == 1)
    D. if (result * sign > INT_MAX && sign == 1)

  3. 如果字符串是"4193 with words"，转换结果是（ ）。
    A. 4193
    B. 0
    C. 4193 with words
    D. 4193with

  4. 如果字符串是"words and 987"，转换结果是（ ）。
    A. 987
    B. 0
    C. words and 987
    D. 错误

  5. 这个算法的时间复杂度是（ ）。
    A. O(n)
    B. O(1)
    C. O(n²)
    D. O(logn)

题目7：最长回文子串 - 程序填空

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

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int start = 0, maxLength = 1;
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    
    // 所有长度为1的子串都是回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    // 检查长度为2的子串
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i+1]) {
            dp[i][i+1] = true;
            start = i;
            maxLength = 2;
        }
    }
    
    // 检查长度大于2的子串
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i+1][j-1]) {
                dp[i][j] = true;
                if (len > maxLength) {
                    start = i;
                    maxLength = len;
                }
            }
        }
    }
    
    return s.substr(start, maxLength);
}

选择题

  1. 动态规划数组dp[i][j]表示（ ）。
    A. 字符串s从i到j的子串是否是回文
    B. 字符串s从i到j的子串的长度
    C. 字符串s从i到j的子串的最长回文长度
    D. 字符串s从i到j的子串的起始位置

  2. 在检查长度大于2的子串时，空白处的代码应该是（ ）。
    A. if (s[i] == s[j] && dp[i+1][j-1])
    B. if (s[i] == s[j] && dp[i][j])
    C. if (s[i] == s[j] && dp[i-1][j-1])
    D. if (s[i] == s[j] && dp[i+1][j])

  3. 对于字符串"babad"，可能的最长回文子串是（ ）。
    A. "bab"
    B. "aba"
    C. 两者都是
    D. 都不是

  4. 这个算法的时间复杂度是（ ）。
    A. O(n)
    B. O(n²)
    C. O(n³)
    D. O(2^n)

  5. 空间复杂度是（ ）。
    A. O(1)
    B. O(n)
    C. O(n²)
    D. O(nlogn)

题目8：字符串的排列检查 - 程序填空

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

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    vector<int> count1(26, 0), count2(26, 0);
    for (char c : s1) {
        count1[c - 'a']++;
    }
    
    int left = 0;
    for (int right = 0; right < s2.size(); right++) {
        count2[s2[right] - 'a']++;
        if (right - left + 1 == s1.size()) {
            if (count1 == count2) return true;
            count2[s2[left] - 'a']--;
            left++;
        }
    }
    return false;
}

选择题

  1. 这个算法用于检查（ ）。
    A. s2是否包含s1的排列
    B. s2是否包含s1的子串
    C. s2是否包含s1的所有字符
    D. s2是否包含s1的逆序

  2. 滑动窗口的大小是（ ）。
    A. s1的长度
    B. s2的长度
    C. 26
    D. 不固定

  3. 如果s1="ab", s2="eidboaoo"，返回值是（ ）。
    A. true
    B. false

  4. 这个算法的时间复杂度是（ ）。
    A. O(n)
    B. O(n²)
    C. O(1)
    D. O(26)

  5. 空间复杂度是（ ）。
    A. O(1)
    B. O(n)
    C. O(26)
    D. O(52)

题目9：最长无重复字符子串 - 程序填空

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

int lengthOfLongestSubstring(string s) {
    vector<int> lastIndex(256, -1);
    int maxLength = 0;
    int start = -1;
    for (int i = 0; i < s.size(); i++) {
        if (lastIndex[s[i]] > start) {
            start = lastIndex[s[i]];
        }
        lastIndex[s[i]] = i;
        maxLength = max(maxLength, i - start);
    }
    return maxLength;
}

选择题

  1. 数组lastIndex用于记录（ ）。
    A. 每个字符第一次出现的位置
    B. 每个字符最后一次出现的位置
    C. 每个字符是否出现过
    D. 每个字符的出现次数

  2. 当遇到重复字符时，start的更新规则是（ ）。
    A. start = lastIndex[s[i]]
    B. start = i
    C. start = lastIndex[s[i]] + 1
    D. start = i + 1

  3. 对于字符串"abcabcbb"，最长无重复字符子串的长度是（ ）。
    A. 3
    B. 4
    C. 5
    D. 6

  4. 这个算法的时间复杂度是（ ）。
    A. O(n)
    B. O(n²)
    C. O(1)
    D. O(256)

  5. 空间复杂度是（ ）。
    A. O(1)
    B. O(n)
    C. O(256)
    D. O(26)

题目10：字符串相加（大数加法）- 程序填空

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

string addStrings(string num1, string num2) {
    int i = num1.size() - 1, j = num2.size() - 1;
    int carry = 0;
    string result;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) {
            sum += num1[i] - '0';
            i--;
        }
        if (j >= 0) {
            sum += num2[j] - '0';
            j--;
        }
        carry = sum / 10;
        result.push_back(sum % 10 + '0');
    }
    reverse(result.begin(), result.end());
    return result;
}

选择题

  1. 算法从字符串的（ ）开始计算。
    A. 开头
    B. 结尾
    C. 中间
    D. 任意位置

  2. 变量carry表示（ ）。
    A. 当前位的和
    B. 进位
    C. 当前位的值
    D. 当前位的数字

  3. 结果字符串最后需要反转是因为（ ）。
    A. 我们从低位开始计算，但字符串需要高位在前
    B. 字符串只能反转存储
    C. 反转后计算更方便
    D. 题目要求

  4. 如果输入是"999"和"1"，结果是（ ）。
    A. "1000"
    B. "100"
    C. "1001"
    D. "9991"

  5. 这个算法的时间复杂度是（ ）。
    A. O(n)
    B. O(n²)
    C. O(1)
    D. O(logn)

  1. 评测队列
  2. 服务状态
  3. Online User
  4. Language
  5. 兼容模式
  6. 主题
  2. 陕ICP备2025061476号
  3. Powered by BitWorld DD