ac记录

#include <bits/stdc++.h>
using namespace std;
string s[25];
int com[25][25];
int n;
char st;
int fans = 0;
unordered_map<string,int> ans;
unordered_map<string,int> cnt;
bool judgeInc(string a,string b){
    string smin,smax;
    if(a.length()<b.length())   {smin = a;smax = b;}
    else    {smin = b;smax = a;}
    for(int i=0;i<smin.length();i++){
        if(smin[i]!=smax[i])    return 0;
    }
    return 1;
}
int searchPrev(string a){
    if(a.length()==1)   return a[0]-'0';
    else{
        int n = a[a.length()-1]-'0';
        if(a[a.length()-2]!='.')    n+=(a[a.length()-2]-'0')*10;
        return n;
    }
}
int find_str(int son,string par){
    int now = 0;
    int cnt = 0;
    for(int i=0;i<par.length();i++){
        if(par[i]=='.'){
            if(now==son)    cnt++;
            if(cnt>1)  break;
            now = 0;
        }
        else{
            if(now==0)  now+=(par[i]-'0');
            else    now+=(par[i]-'0')*10;
            if(i==par.length()-1){
                if(now==son)    cnt++;
            }
        }
    }
    return cnt;
}
void bfs(){
    queue<string> q;
    string now;
    for(int i=1;i<=n;i++){
        if(s[i][0]==st){
            now = to_string(i);
            q.push(now);
            cnt[now] = 1;
            ans[now] = s[i].length();
            if(fans<ans[now])   fans = ans[now];
        }
    }
    string ns;
    int pos;
    while(!q.empty()){
        now = q.front();
        q.pop();
        // cout << now << "\n";
        for(int j=1;j<=n;j++){
            pos = searchPrev(now);
            // cout << pos << "p" << "\n";
            // if(now=="1.2.3.2.3.5.5" && j==5)    cout << find_str(j,now) << "\n";
            if(find_str(j,now)<=1){
                ns = now+"."+to_string(j);
                if(com[pos][j]){
                    q.push(ns);
                    ans[ns] = ans[now]+(s[j].length()-com[pos][j]);
                    cnt[ns] = cnt[now]+1;
                    // cout << pos << " " <<j << " " << com[pos][j] << "\n";
                    if(ans[ns]>fans)    fans = ans[ns];
                }
            }
        }
    }
}
// void dfs()
int main(){
    memset(com,0,sizeof(com));
    cin >> n;
    for(int i=1;i<=n;i++)   cin >> s[i];
    cin >> st;
    int maxdel;
    for(int j=1;j<=n;j++){
        for(int k=1;k<=n;k++){
            if(judgeInc(s[j],s[k]) && s[j]!=s[k]) com[j][k] = 0;
            else{
                maxdel = max(s[j].length(),s[k].length())-min(s[j].length(),s[k].length());
                for(int c=min(s[j].length(),s[k].length())-1;c>=1;c--){
                    if(s[j].substr(s[j].length()-c,c)==s[k].substr(0,c)){
                        com[j][k] = c;
                        // break;
                    }
                }
            }
        }
    }
    bfs();
    cout << fans;
    return 0;
}