[NOIP2000 提高组] 单词接龙

#include <bits/stdc++.h>
using namespace std;
int n;
string s[25];
char c;
int lnk[25][25];
int ans;
int cnt[25];
void dfs(int now, int len)
{
    ans = max(ans, len);
    for (int i = 1; i <= n; i++)
    {
        //cout << now << " " << i << " " << cnt[i] << " " << lnk[now][i] << endl;
        if (cnt[i] < 2 && lnk[now][i])
        {
            cnt[i]++;
            //cout << s[now] << "~" << s[i] << endl;
            dfs(i, len + s[i].length() - lnk[now][i]);
            cnt[i]--;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    cin >> c;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            lnk[i][j] = 0;
            for (int k = s[i].length() - 1; k > 0; k--)
            {
                bool flag = true;
                for (int p = k; p <= s[i].length() - 1; p++)
                    if (s[i][p] != s[j][p - k])
                    {
                        flag = false;
                        break;
                    }
                if (flag)
                {
                    lnk[i][j] = s[i].length() - 1 - k + 1;
                    break;
                }
            }
        }
    }
    ans = 0;
    for (int i = 1; i <= n; i++)
        if (s[i][0] == c)
        {
            cnt[i]++;
            dfs(i, s[i].length());
            cnt[i]--;
        }
    cout << ans << endl;
    return 0;
}