/** 题目：UVALive 7712 Confusing Manuscript 链接：https://vjudge.net/problem/UVALive-7712 题意：给定n个不同的字符串，f(i)表示第i个字符串和其他字符串的编辑距离为1的个数。 编辑距离为1表示两个字符串其中一个可以通过删除任意位置某一个字符或者增加任意位置某一个字符或者替换任意位置某一个字符之后，两者匹配。 输出f(i)最大的字符串，如果f(i)==f(j) (i<j) 输出第i个字符串。 思路：字典树 主要是处理细节。首先插入所有字符串。 然后枚举处理每个字符串s，对当前s，先从字典树删除它，然后query，最后插回字典树。 主要是query细节，以下都是对当前s进行处理： int query(int u,char *s,int pos,int mofa) ； mofa表示当前是否进行以下三种操作任意一种。 1，add 可以直接和当前字典树的某个匹配，自身pos不加。 特殊情况：如果s[pos]==' ';那么直接找字典树当前位置上存在的叶子节点。 2，cut 字典树当前位置不变，s的pos+1； 特殊情况：s[pos+1]==' ';那么删除当前就没有了，所以计算结果为pos-1那一层的叶子节点。 实际上就是当前的u，判断val[u]就可以知道是否是叶子节点。 3，replace 直接替换。 */ #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<vector> #include<queue> #include<cstring> #include<cmath> using namespace std; typedef pair<int,int> P; typedef long long LL; const int INF = 0x3f3f3f3f; const int maxnode = 50000*10+10;///最多可能有多少个节点 const int maxn = 5e4+10; const int sigma_size = 26;///0或者1 int ch[maxnode][sigma_size];///由于很大，所以结构体内部放不下。要放在外面。 char s[maxn][11]; int ans = 0; int anspos; struct Trie{ int val[maxnode]; int sz; int idx(char c){return c-'a';} void insert(char *s) { int u = 0, c; for(int i = 0; s[i]!=' '; i++){ c = idx(s[i]); if(!ch[u][c]){ memset(ch[sz], 0, sizeof ch[sz]); ch[u][c] = sz; val[sz++] = 0; } u = ch[u][c]; } val[u]=1;///表示该节点存在该单词。 } void del(char *s) { int u = 0, c; for(int i = 0; s[i]!=' '; i++){ c = idx(s[i]); u = ch[u][c]; } val[u]=0; } int query(int u,char *s,int pos,int mofa) { int c = idx(s[pos]);; int cnt = 0; if(mofa==0){ if(ch[u][c]==0) return 0; if(s[pos+1]==' '){ return val[ch[u][c]]; }else { return query(ch[u][c],s,pos+1,0); } }else { ///add if(s[pos]==' '){ for(int i = 0; i < 26; i++){ if(ch[u][i]) cnt += val[ch[u][i]]; } return cnt;///不可以再进行删除和替换操作了。 }else{ for(int i = 0; i < 26; i++){ if(ch[u][i]==0) continue; cnt += query(ch[u][i],s,pos,0); } } ///cut if(s[pos+1]==' '){ cnt += val[u]; }else cnt += query(u,s,pos+1,0); ///replace for(int i = 0; i < 26; i++){ if(ch[u][i]==0) continue; if(i!=c){ if(s[pos+1]==' '){ cnt += val[ch[u][i]]; }else cnt += query(ch[u][i],s,pos+1,0); } } ///bu bian if(ch[u][c]){ cnt += query(ch[u][c],s,pos+1,1); } return cnt; } } }; int main() { int T, n; Trie trie; int cas = 1; cin>>T; while(T--) { scanf("%d",&n); trie.sz = 1; memset(ch[0], 0, sizeof ch[0]); for(int i = 0; i < n; i++){ scanf("%s",s[i]); trie.insert(s[i]); } ans = 0, anspos = 0;//! for(int i = 0; i < n; i++){ trie.del(s[i]); int temp = trie.query(0,s[i],0,1); //cout<<s[i]<<endl; //cout<<temp<<endl; if(temp>ans){ ans = temp; anspos = i; } trie.insert(s[i]); } printf("Case #%d: %s ",cas++,s[anspos]); } return 0; }