AcWing 1117. 单词接龙

时隔n年练习string 的自带函数,完全不记得substr了....

思路:

         首先注意重叠部分的长度使用是任意的.预处理出每个字符串之间重叠的最短长度.然后dfs相连即可.

判定前后缀是否相等用substr较为方便.主要有两种用法 Go

         因为重合部分不能超过原字符串长,所以直接对比字符串之间的重叠部分即可.

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 using namespace std;
 5 const int N = 25;
 6 int n,cnt[N],ans,g[N][N];
 7 string s[N];
 8 void dfs(int x,int len)
 9 {
10     ans = max(ans,len);
11     for(int i=1;i<=n;i++)
12     {
13         int l1 = s[x].size(),l2 = s[i].size();
14         if(g[x][i]&&cnt[i]<2)
15         {
16             cnt[i]++;
17             dfs(i,len+l2-g[x][i]);
18             cnt[i]--;
19         }
20     }
21 }
22 void inits()
23 {
24     for(int i=1;i<=n;i++)
25       for(int j=1;j<=n;j++)
26       {
27           string a = s[i],b = s[j];
28           for(int k=1;k<min(a.size(),b.size());k++)
29               if(a.substr(a.size()-k,k)==b.substr(0,k))
30               {
31                   g[i][j] = k;
32                   break;
33               }
34       }
35 }
36 int main()
37 {
38     scanf("%d",&n);
39     char head[5];
40     for(int i=1;i<=n;i++) cin>>s[i];
41     scanf("%s",head);
42     inits();
43     for(int i=1;i<=n;i++)
44     {
45         if(s[i][0]==head[0])
46         {
47             cnt[i]++;
48             dfs(i,(int)s[i].size());
49             cnt[i]--;
50         }
51     }
52     printf("%d\n",ans);
53     return 0;
54 }