CSP-J 入门级 · CSP 2023 入门级第一轮 第 17 题

2.

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

int f(string x,string y){
    int m=x.size();
    int n=y.size();
    vector<vector<int>>v(m+1,vector<int>(n+1,0));
    for(int i=1;i<=m;i++){
       for(int j=1;j<=n;j++){
            if(x[i-1]==y[j-1]){
                v[i][j]=v[i-1][j-1]+1;
            }else{
                v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        }
    }
    return v[m][n];
}
bool g(string x,string y){
    if(x.size() != y.size()){
        return false;
    }
    return f(x+x,y)==y.size();
}
int main(){
    string x,y;
    cin>>x>>y;
    cout<<g(x,y)<<endl;
    return 0;
}

判断题

1. f 函数的返回值小于等于 $\min\{n,m\}$。（）

2. f 函数的返回值等于两个输入字符串的最长公共子串的长度。（）

3. 当输入两个完全相同的字符串时，g 函数的返回值总是 true。（）

单选题

4. 将第19行中的 v[m][n] 替换为 v[n][m]，那么该程序（）。

5. 当输入为 csp-j p-jcs 时，输出为（）。

6. 当输入为 csppsc spsccp 时，

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

先识别 f 是 LCS 动态规划，再理解 g 的本质：把 x 自拼一次看 y 是否是其子序列且长度相等。做题时先算 f 的返回值范围，再代入具体字符串模拟匹配，最后检查数组越界风险。

最容易把 f 当成求最长公共子串，其实 f 求的是子序列，两者区别很大。其次，看到 g 里的 x+x 容易以为是在找连续子串，其实 f 找的是子序列，只要顺序对就行。还有，改 v[m][n] 为 v[n][m] 时，若 m 和 n 不等，访问 v[n][m] 会越界，很多学生会忽略这一点。

这道题主要考查字符串处理、动态规划（LCS）以及函数逻辑的综合运用。命题人通过一段看似复杂的代码，把 LCS 算法和字符串循环子序列判断包装在一起，既考基础又考细节。f 函数用经典的二维 DP 求最长公共子序列长度，g 函数则巧妙利用 x+x 来模拟循环移位，判断 y 能否作为 x 的循环子序列出现。题目里的陷阱不少，比如把子序列和子串混淆，或者改代码时忽略数组越界。下面逐题拆解。

f 函数的返回值一定小于等于 min(n,m)，因为子序列长度不可能超过原字符串中较短的那个。这是 DP 的基本性质，也是第一个判断题的答案。第二个判断题说 f 返回的是最长公共子串长度，这显然是错的，f 求的是子序列，子串要求连续，两者完全不同。第三个判断题，当两个字符串完全相同时，g 函数会返回 true，因为 f(x+x, x) 的长度就是 x 的长度，满足条件。

第四个单选题，把 v[m][n] 改成 v[n][m]，如果 m 和 n 不相等，访问 v[n][m] 就会越界，因为 v 的维度是 (m+1)×(n+1)，所以程序可能非正常退出，选 D。这个改动看似只是交换行列，实则破坏了数组边界，是命题人特意挖的坑。

第五个单选题，输入 csp-j 和 p-jcs。x+x 是 csp-jcsp-j，长度 8，y 长度 5。f 计算 LCS 长度，p-jcs 作为子序列在 x+x 中确实存在，比如 p(2)-(3)j(4)c(5)s(6)，长度 5 等于 y 的长度，所以 g 返回 true，输出 1，选 B。这里要注意，虽然 p-jcs 不是连续子串，但作为子序列是合法的，f 的 DP 会正确算出长度。

第六个单选题，输入 csppsc 和 spsccp。同样，x+x 是 csppsc csppsc，长度 10，y 长度 6。f 计算 LCS 长度，spsccp 作为子序列在 x+x 中存在，长度 6 等于 y 的长度，所以 g 返回 true，输出 1，选 D。这个例子也说明，只要子序列匹配成功，g 就返回 true，与是否连续无关。

从考频来看，字符串相关题目在 CSP 入门级出现过 6 次，函数定义与调用在入门级出现过 7 次，动态规划在入门级出现过 22 次，都是高频考点。近年来动态规划题目数量持续上升，2025 年入门级就有 25 道，2026 年更是达到 30 道，说明这类题目越来越受命题人青睐。字符串与函数结合的题目虽然不多，但一旦出现，往往就是压轴题，考察综合能力。未来可能继续以这种组合形式出现，比如加入更多字符串操作或更复杂的 DP 状态转移。