题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeastbeast和astonishastonishastonish，如果接成一条龙则变为beastonishbeastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atatat 和 atideatideatide 间不能相连。
输入输出格式
输入格式：
输入的第一行为一个单独的整数nnn (n≤20n \le 20n≤20)表示单词数，以下nnn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：
只需输出以此字母开头的最长的“龙”的长度
本题我本来打算在深搜的时候在处理两个单词的相交部分，但发现预处理一下会更好
要注意使用string变量求其长度与char变量求长度有所不同；
string a; int length=a.size(); //注意此处不是size(a)，一开始我在VScode上编译竟没报错，然后提交洛谷评测，成功CE。。。
char a; int length=strlen(a);
代码如下：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define maxn 1010 9 #define ll long long10 #define IL inline11 #define clear(a) memset(a,0,sizeof a)12 IL void read(int &x)13 {14 x = 0;int f = 1;char ch = getchar();15 while(ch<'0'||ch>'9'){ if(ch=='-')f = -f;ch = getchar();}16 while(ch>='0'&&ch<='9'){x = x * 10 + ch - '0', ch = getchar();}x *= f;17 }18 19 int n, ans;20 char head;21 int color[maxn], used[maxn];22 int contact[maxn][maxn];23 string z[maxn];24 25 void solve(int x,int y)26 {27 for (int i = 1; i <= min(z[x].size(), z[y].size()) - 1; i++)28 {29 int lazy = 0;30 int pry = 0;31 for (int j = z[x].size() - i; j <= z[x].size() - 1;j++)32 {33 if(z[x][j]==z[y][pry])34 pry++;35 else36 {37 lazy = 1;38 break;39 }40 }41 if(lazy)42 continue;43 else44 {45 contact[x][y] = i;46 break;47 }48 }49 }50 51 void dfs(int id,int length)52 {53 ans = max(ans, length);54 for (int i = 1; i <= n;i++)55 {56 if(color[i]>=2)57 continue;58 if(contact[id][i])59 {60 color[i]++;61 dfs(i, length+z[i].size()-contact[id][i]);62 color[i]--;63 }64 }65 ans = max(ans, length);66 }67 68 int main()69 {70 read(n);71 for (int i = 1; i <= n;i++)72 cin >> z[i];73 cin >> head;74 for (int i = 1; i <= n;i++)75 for (int j = 1; j <= n;j++)76 solve(i, j);77 for (int i = 1; i <= n; i++)78 if (z[i][0] == head)79 {80 color[i] = 1;81 dfs(i, z[i].size());82 color[i] = 0;83 }84 cout << ans;85 return 0;86 }