CSP-J 2023 第一轮 第 24 题：程序（二）：把 v[m][n] 换成 v[n][m] 会怎样

题目

#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;
}

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

选项

• A. 行为不变
• B. 只会改变输出
• C. 一定非正常退出
• D. 可能非正常退出

答案

D

题解

选 D．可能非正常退出。关键是：交换下标后可能越界，但越界不一定导致程序退出。

v 的定义是： ``cpp vector<vector<int>> v(m+1, vector<int>(n+1, 0)); ` 因此，第一维合法下标是 0～m，第二维合法下标是 0～n`。

分两种情况看：

• x、y 长度不同：g 直接返回 false，不调用 f，程序正常输出 0。
• x、y 长度相同：设长度为 k > 0。调用的是 f(x+x, y)，所以函数内 m=2k、n=k。修改后访问：

``cpp v[n][m] // 即 v[k][2*k] ` 第二维最大合法下标只有 k，访问 2*k` 越界。

C++ 中，vector 的 [] 不做边界检查，越界访问属于未定义行为：可能异常退出，也可能暂时没有崩溃，所以不能选“一定非正常退出”。

注意：虽然最长公共子序列的长度满足 f(x,y)=f(y,x)，但这并不意味着同一个表中的 v[m][n] 可以换成 v[n][m]。