NOIP2000提高组复赛C 单词接龙

题目链接：https://ac.nowcoder.com/acm/contest/248/C

题目大意：

　　略

分析：

　　注意点：1.前缀和后缀的公共部分应该选最短的。2.如果两个字符串前缀和后缀的公共部分恰好是其中一个字符串，那么这两个字符串不能合并。

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 #define rep(i,n) for (int i = 0; i < (n); ++i)

 #define For(i,s,t) for (int i = (s); i <= (t); ++i)

 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)

 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

 #define pr(x) cout << #x << " = " << x << "  "

 #define prln(x) cout << #x << " = " << x << endl

 #define ALL(x) x.begin(),x.end()

 #define INS(x) inserter(x,x.begin())

 #define ms0(a) memset(a,0,sizeof(a))

 #define msI(a) memset(a,inf,sizeof(a))

 #define pii pair<int,int>

 #define piii pair<pair<int,int>,int>

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 inline int gc(){

     static const int BUF = 1e7;

     static char buf[BUF], *bg = buf + BUF, *ed = bg;

     if(bg == ed) fread(bg = buf, , BUF, stdin);

     return *bg++;

 }

 inline int ri(){

     int x = , f = , c = gc();

     for(; c<||c>; f = c=='-'?-:f, c=gc());

     for(; c>&&c<; x = x* + c - , c=gc());

     return x*f;

 }

 typedef long long LL;

 const int maxN = 1e5 + ;

 int n, ans;

 string str[];

 vector< pii > nexts[];

 int cnt[];

 string st;

 // Common prefix and suffix

 int CPS(int x, int y) {

     int ret = , i = str[x].size()-, j = ;

     while(i >=  && j < str[y].size()){

         if(str[x].substr(i, str[x].size()) == str[y].substr(, j)) {

             ret = j;

             break;

         }

         --i;

         ++j;

     }

     if(ret == str[x].size() || ret == str[y].size()) ret = ;

     return ret;

 }

 void dfs(int x, int ret) {

     bool flag = true;

     rep(i, nexts[x].size()) {

         int nt = nexts[x][i].se;

         if(cnt[nt] >= ) continue;

         flag = false;

         ++cnt[nt];

         dfs(nt, ret + str[nt].size() - nexts[x][i].fi);

         --cnt[nt];

     }

     if(flag) ans = max(ans, ret);

 }

 int main(){

     scanf("%d", &n);

     For(i, , n) cin >> str[i];

     cin >> st;

     For(i, , n) {

         For(j, , n) {

             int t = CPS(i, j);

             if(t) nexts[i].push_back(mp(t, j));

         }

     }

     For(j, , n) {

         if(st[] == str[j][])nexts[].push_back(mp(, j));

     }

     dfs(, );

     printf("%d\n", ans);

     return ;

 }