題目描述

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

輸入輸出格式

輸入格式：

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

輸出格式：

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

輸入輸出樣例

輸入樣例#1：

5
at
touch
cheat
choose
tact
a

輸出樣例#1：

23

說明

連成的“龍”為atoucheatactactouchoose

源代碼

# include<iostream> # include<cstdio> # include<string> using namespace std; int n; string str[30]; int len_str,sum=0; int times[30]={0};//存儲單詞出現(xiàn)次數(shù)void dfs(int x) {int i,j;int p,q;int num;//存儲不匹配的字符串個數(shù)int work;for(i=1;i<str[x].length();i++){num=0;for(j=1;j<=n;j++){if(times[j]<2)//出現(xiàn)次數(shù)少于2次{if(str[x][i]==str[j][0])//依次比較當前字符串與字符串[j]的頭是否相同{p=i,q=0,work=0;while(p<=str[x].length()-1)//相同繼續(xù)比較{if(str[x][p]!=str[j][q])//如果不同{num++;//不匹配的字符串個數(shù)+1work++;break;//終止}p++;q++;}if(!work&&q!=str[j].length())//符合條件，進行操作{len_str+=str[j].length()-q;//累加長度times[j]++;//累加次數(shù)dfs(j);//繼續(xù)向下搜索len_str-=str[j].length()-q;//還原長度times[j]--;//還原次數(shù)}}else num++;//不同，不匹配的字符串個數(shù)+1}else num++;//大于兩次，不匹配的字符串個數(shù)+1}if(num==n&&i==str[x].length()-1)//當不匹配個數(shù)與所給個數(shù)相同并且長度與所給的長度相同時{if(sum<len_str) sum=len_str;//如果最大長度小于字符串長度，令最大長度等于字符串長度return;}} } int main() {int i;cin>>n;//輸入單詞個數(shù)nfor(i=1;i<=n+1;i++) cin>>str[i];//輸入n個單詞for(i=1;i<=n;i++)//令最后一個單詞為龍頭，尋找以龍頭開頭的字符串if(str[i][0]==str[n+1][0]){times[i]++;//找到后，出現(xiàn)次數(shù)+1len_str=str[i].length();//記錄字符串長度dfs(i);//開始搜索}cout<<sum<<endl;//輸出最長長度return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的单词接龙（洛谷-P1019）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。