題目描述

單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如?beast?和?astonish，如果接成一條龍則變為?beastonish，另外相鄰的兩部分不能存在包含關系，例如?at?和?atide?間不能相連。

輸入格式

輸入的第一行為一個單獨的整數?n?表示單詞數，以下?n?行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在。

輸出格式

只需輸出以此字母開頭的最長的“龍”的長度。

輸入輸出樣例

輸入?

5
at
touch
cheat
choose
tact
a

輸出?

23

說明/提示

樣例解釋：連成的“龍”為?atoucheatactactouchoose。

n≤20。

解題思路

這道題要求兩個字符串要有連接部分，但是又不能互相包含，并且每個字符串使用不能超過兩次，最后將所有字符串連起來后計算最后字符串的總長度然后輸出

題目要求首個字母必須是c，那么我們輸入所有字符串后先查詢有沒有首字母和c相同的，那么就以這個為龍頭進行dfs

在dfs函數中，我們可以先存入字符串的長度，隨后在循環中查找符合要求的字符串，在查詢每一個字符串后記得標記，如果訪問次數大于2那就跳過。

查詢字符串時，我們可以使用substr函數進行剪切，如果符合要求那就返回剪切后的字符串，如果找不到符合要求的就返回“0”，在dfs函數中也要記得判斷一下更新后的字符串是否為“0”，如果不為0才可以繼續進行dfs

完整代碼如下：

#include<bits/stdc++.h>
using namespace std;
int n,mark[30]={0},sum=0;
string s[30];
string pd(string len1,string len2)
{int a=len1.size(),b=len2.size();for(int i=1;i<a&&i<b;i++){if(len1.substr(a-i,i)==len2.substr(0,i)){return len1.substr(0,a-i)+len2;}}return "0";
}
void dfs(string drag)
{if(sum<drag.size()){sum=drag.size();} for(int i=0;i<n;i++){if(mark[i]<2){string stl=pd(drag,s[i]);if(stl!="0"){mark[i]++;dfs(stl);mark[i]--;}}}
}
int main()
{char c;cin>>n;for(int i=0;i<n;i++){cin>>s[i];}cin>>c;for(int i=0;i<n;i++){if(s[i][0]==c){mark[i]++;dfs(s[i]);mark[i]--;}}cout<<sum;return 0;
}