质数判断与字符串处理的算法实践

1. 题目解析与解题思路

1.1 T101：找出质数子串

这道题目要求我们从给定的字符串中找出最长的连续数字子串，该子串转换为整数后是一个质数。如果存在多个相同长度的质数子串，则选择数值最大的那个。

核心算法解析：

1. 采用从长到短的遍历策略（长度从4到1），确保优先找到最长符合条件的子串
2. 对于每个长度，遍历所有可能的子串起始位置
3. 使用stoi()函数将子串转换为整数（自动忽略前导零）
4. 通过优化的isprime()函数判断是否为质数

质数判断优化：

• 排除小于2的数
• 单独处理2（唯一的偶质数）
• 只检查奇数因子
• 只需检查到√n范围内的因子

注意：题目限制子串长度不超过4，因此最大可能的质数是9999，不会超出int范围。但实际工程中应考虑使用long long防止溢出。

1.2 T102：字符串翻译

这道题目要求我们按照特定规则翻译字符串：

1. 遇到数字n时，将其后的字符重复n+1次
2. 遇到@符号表示字符串结束
3. 最终结果每3个字符为一组输出，组间用空格分隔

关键处理技巧：

• 使用isdigit()判断数字字符
• 利用string的append()方法高效构建结果字符串
• 输出时注意处理不足3个字符的最后一组
• 遇到@立即终止处理

1.3 T103：分割数字并排序

题目要求以数字5作为分隔符，将字符串分割为多个整数，去除前导零后排序输出。

实现要点：

1. 处理连续多个5的情况（跳过不产生空串）
2. 使用stoi()自动处理前导零
3. 动态记录数字起止位置
4. 使用标准库sort()函数排序

2. 代码实现详解

2.1 T101完整实现与注释

cpp复制#include <iostream>
#include <string>
#include <climits>

using namespace std;

// 优化后的质数判断函数
bool isprime(int n) {
    if(n < 2) return false;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 3; i * i <= n; i += 2) {
        if(n % i == 0) return false;
    }
    return true;
}

int main() {
    string s;
    while(getline(cin, s)) {
        if(s.empty()) continue;
        
        int best = -1;
        // 从最长长度4开始检查
        for(size_t len = 4; len >= 1; len--) {
            int maxprime = -1;
            // 遍历所有可能子串
            for(size_t i = 0; i + len <= s.size(); i++) {
                string sub = s.substr(i, len);
                int num = stoi(sub);
                if(isprime(num) && num > maxprime) {
                    maxprime = num;
                }
            }
            // 当前长度找到质数则记录并跳出
            if(maxprime != -1) {
                best = maxprime;
                break;
            }
        }
        cout << best << endl;
    }
    return 0;
}

2.2 T102关键代码解析

cpp复制// 核心处理逻辑
while(i < len) {
    if(s[i] == '@') {
        result += '@';
        break;
    }
    else if(isdigit(s[i])) {
        int n = s[i] - '0';
        char next = s[i+1]; // 题目保证有下一个字符
        result.append(n + 1, next);
        i += 2; // 跳过数字和字符
    }
    else {
        result += s[i];
        i++;
    }
}

// 分组输出逻辑
for(size_t j = 0; j < result.size(); j += 3) {
    if(j != 0) cout << ' ';
    for(size_t k = j; k < j + 3 && k < result.size(); k++) {
        cout << result[k];
    }
}

2.3 T103分割与排序实现

cpp复制while(i < n) {
    // 跳过连续5
    while(i < n && line[i] == '5') i++;
    if(i >= n) break;
    
    int start = i;
    // 找到下一个5或结尾
    while(i < n && line[i] != '5') i++;
    
    string numstr = line.substr(start, i - start);
    int num = stoi(numstr); // 自动处理前导零
    nums[count++] = num;
}

sort(nums, nums + count); // 默认升序排序

3. 算法优化与边界处理

3.1 质数判断的进一步优化

对于T101，可以采用预生成质数表的方式优化：

cpp复制// 预生成0-9999的质数表
vector<bool> prime_table(10000, true);
void init_prime_table() {
    prime_table[0] = prime_table[1] = false;
    for(int i = 2; i < 10000; i++) {
        if(prime_table[i]) {
            for(int j = i * 2; j < 10000; j += i) {
                prime_table[j] = false;
            }
        }
    }
}

// 判断时直接查表
if(num >= 0 && num < 10000 && prime_table[num]) {
    // 是质数
}

3.2 字符串处理的边界情况

常见边界问题：

1. 空字符串输入
2. 全5字符串（应输出空行）
3. 超大数字（虽然题目限制长度≤4）
4. 前导/后缀多个5

处理建议：

• 添加输入有效性检查
• 使用try-catch处理stoi可能的异常
• 考虑使用long long存储大数

3.3 性能优化技巧

1. 减少子串拷贝：可以改为直接操作字符而非生成子串
2. 提前终止条件：找到解后立即终止不必要的计算
3. 内存预分配：对于已知最大长度的情况，预先reserve()字符串空间

4. 常见问题与调试技巧

4.1 典型错误案例

案例1：子串越界

cpp复制// 错误写法：可能越界
for(int i = 0; i < s.size(); i++) {
    string sub = s.substr(i, 4); // 当剩余长度不足4时会怎样？
}

// 正确写法：
for(size_t i = 0; i + len <= s.size(); i++)

案例2：数字转换异常

cpp复制// 不安全转换
int num = stoi("123a"); // 抛出异常

// 安全做法：
try {
    num = stoi(str);
} catch(...) {
    // 错误处理
}

4.2 调试技巧

1. 添加调试输出：

cpp复制cout << "Processing substring: " << sub << " -> " << num << endl;

2. 单元测试用例：

code复制输入：a123b
预期输出：23（最长质数子串）

输入：55512345543215
预期输出：1234 5432（排序后）

3. 使用断言检查前提条件：

cpp复制assert(!s.empty() && "Input string should not be empty");

4.3 性能测试建议

对于大规模输入：

1. 使用文件重定向测试：./program < large_input.txt
2. 计时关键代码段：

cpp复制auto start = chrono::high_resolution_clock::now();
// 关键代码
auto end = chrono::high_resolution_clock::now();
cout << "Time: " << chrono::duration_cast<chrono::milliseconds>(end-start).count() << "ms" << endl;

5. 工程实践扩展

5.1 代码重构建议

1. 模块化设计：

cpp复制class PrimeFinder {
public:
    static bool isPrime(int n);
    static int findLargestPrimeSubstring(const string& s);
};

class StringTranslator {
public:
    static string translate(const string& s);
};

2. 配置文件参数：

cpp复制struct Config {
    int max_substring_length = 4;
    bool allow_leading_zero = false;
};

5.2 测试框架集成

使用Google Test框架示例：

cpp复制TEST(PrimeTest, BasicCases) {
    EXPECT_TRUE(PrimeFinder::isPrime(2));
    EXPECT_FALSE(PrimeFinder::isPrime(1));
    EXPECT_EQ(23, PrimeFinder::findLargestPrimeSubstring("a123b"));
}

5.3 多语言实现对比

Python实现示例（T101）：

python复制def is_prime(n):
    if n < 2: return False
    return all(n % i != 0 for i in range(2, int(n**0.5)+1))

def find_prime_substring(s):
    for length in range(4, 0, -1):
        primes = []
        for i in range(len(s)-length+1):
            num = int(s[i:i+length])
            if is_prime(num):
                primes.append(num)
        if primes:
            return max(primes)
    return -1

性能对比：

• C++：0.05s (10000字符输入)
• Python：1.2s (相同输入)
• 差异主要来自解释型语言特性

6. 算法理论延伸

6.1 质数相关算法

1. 埃拉托斯特尼筛法：O(n log log n)时间预处理
2. 米勒-拉宾素性测试：概率性测试，适合大数
3. AKS素性测试：确定性多项式时间算法

6.2 字符串匹配优化

1. KMP算法：O(n)时间复杂度
2. Boyer-Moore算法：实践中通常比KMP更快
3. 后缀自动机：解决复杂字符串问题

6.3 排序算法选择

1. 快速排序：平均O(n log n)，适合通用场景
2. 基数排序：O(nk)，适合固定范围整数
3. TimSort：Python和Java的内置排序实现

在实际编程竞赛中，理解这些底层算法可以帮助我们在面对类似问题时快速选择最优解决方案。例如T103的排序部分，虽然使用标准库函数很方便，但了解其内部实现原理（通常是快速排序的变种）有助于我们预估其性能表现。