第十五届蓝桥杯C++B组第二场真题-前缀总分

思路

由于每改变一个字符，对其与其它n-1个字符串的前缀长度都有影响，所以我们需要记录改变前任意两个字符串的前缀长度和其对于每一个位置的后缀情况，当改变后使前缀长度变长的同时，我们还需要考虑其后缀是否也能加到前缀里

#include <bits/stdc++.h>
using namespace std;
const int N = 200+10;
int n,ji;
string a[N];
int pre[N][N],suf[N][N][N];                        //记录任意两个字符串的前缀，以及任意两个字符串在当前位置下的后缀长度
int find(int c,int d){                             //去寻找当前的最长公共子串长度 
    int min_size=min(a[c].size(),a[d].size());
    for(int i=0;i<min_size;i++){
        if(a[c][i]!=a[d][i]) return i;
    }
    return min_size;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){                      //枚举任意两个字符串之间的最长公共前缀
            if(i==j) continue;
            pre[i][j]=find(i,j);
            if(j<i) ji+=pre[i][j];                  //记录当前情况下(即未改变前)的前缀总分 
            for(int k=min(a[i].size(),a[j].size())-1;k>=0;k--){
                if(a[i][k]==a[j][k]) suf[k][i][j]=suf[k+1][i][j]+1; //记录任意两个字符串的公共后缀长度 
                else suf[k][i][j]=0;
            }
        }
    }
    int ans=ji;                                      //先把当前情况下(即未改变前)的前缀总分赋值给答案，方便后续比较 
    for(int i=1;i<=n;i++){                           //遍历所有的字符串i 
        for(int j=0;j<a[i].size();j++){              //遍历所有字符串的每一个位置 
            for(char k='a';k<='z';k++){              //枚举所有改变情况 
                if(k!=a[i][j]){                      //当改变后的字符和原字符不同时进行分析 
                    int t=ji;                        //先记录当前前缀总分 
                    for(int l=1;l<=n;l++){           //遍历对每一个字符串i和字符串l进行比较 
                        if(i!=l){                    //当字符串i和l不是同一字符串时 
                            t-=pre[i][l];            //先把两字符串原来的总分减掉 
                            if(pre[i][l]<j) t+=pre[i][l];   //如果两字符串最长公共前缀长度比其短，即不用改变，加回之前的总分 
                            else if(pre[i][l]==j && k==a[l][j]) t+=pre[i][l]+1+suf[j+1][i][l];    //当它们最长公共前缀正好到这的前一个，刚好变换后的字符和另一个字符串相同，则把它们之前的前缀总分加一并加上它们的相同后缀长度 
                            else t+=j;               //否则就把当前值加回去 
                        }
                    }
                    ans=max(ans,t);
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}