37.（字符串）
有 n 個長為 m+1 的字符串，
如果某個字符串的最后 m 個字符與某個字符串的前 m 個字符匹配，則兩個字符串可以聯接，
問這 n 個字符串最多可以連成一個多長的字符串，如果出現循環，則返回錯誤。

?

分析：如果出現循環，則返回錯誤 這句不懂 我采用了絕對不會產生環的方法來做。

具體做法是先給每個字符串建一個vector 存入每個字符串后面可以匹配的字符串序號

然后遍歷所有的搭配情況，找到最長的。

我的遍歷代碼很丑... 可謂又臭又長..... 深深的自我鄙視。

/* 37.（字符串） 有 n 個長為 m+1 的字符串， 如果某個字符串的最后 m 個字符與某個字符串的前 m 個字符匹配，則兩個字符串可以聯接， 問這 n 個字符串最多可以連成一個多長的字符串，如果出現循環，則返回錯誤。 start time = 18:27 end time = */#include <iostream> #include <vector> #include <string> using namespace std;//判斷兩個字符串能否拼接 0表示不能 2表示s1在前 1表示s2在前 int contact(string s1, string s2, int m) {if(s1.substr(0, m) == s2.substr(s2.length() - m, m))return 1;else if(s2.substr(0, m) == s1.substr(s1.length() - m, m))return 2;elsereturn 0; }void getMax0(vector<int> now, vector<vector<int>> can_compare, vector<int> &max) { bool isfind = false;int last = now.back();vector<int>::iterator it;for(it = can_compare.at(last).begin(); it < can_compare.at(last).end(); it++){bool isHave = false;vector<int>::iterator it2;for(it2 = now.begin(); it2 < now.end(); it2++){if((*it) == (*it2)){isHave = true;break;}}if(isHave == false){isfind = true;now.push_back(*it);getMax0(now, can_compare, max);now.pop_back();}}if(isfind == false){if(now.size() > max.size()){max = now;}} } vector<int> getMax(vector<vector<int>> can_compare) {vector<int> contact;vector<int> max;vector<int> now;vector<vector<int>>::iterator it;for(int i = 0; i < can_compare.size(); i++){now.push_back(i);getMax0(now, can_compare, max);now.clear();}return max; }//返回可能的最大長度 string maxLength(vector<string> S, int m) {//找到每個字符串在前時有哪些其他字符串可以與其匹配vector<vector<int>> can_compare;vector<string>::iterator it;for(it = S.begin(); it < S.end(); it++){vector<int> can_member;vector<string>::iterator it2;int n = 0;for(it2 = S.begin(); it2 < S.end(); it2++){if(it != it2){if(contact(*it, *it2, m) == 2){can_member.push_back(n);}}n++;}can_compare.push_back(can_member);}vector<int> maxStringMember = getMax(can_compare);vector<int>::iterator it3;string ans = S.at(maxStringMember.at(0));for(it3 = maxStringMember.begin() + 1; it3 < maxStringMember.end(); it3++){string after = S.at(*it3);ans.append(after.substr(after.length() - 1, 1));}cout << "the max length is "<< ans.length() << endl;cout << "the string is " << ans << endl;return ans; }int main() {vector<string> S;string s1 = "abd";S.push_back(s1);string s2 = "bcd";S.push_back(s2);string s3 = "cde";S.push_back(s3);string s4 = "def";S.push_back(s4);string ans = maxLength(S, 2);return 0; }

?

在網上看答案，發現這是一道圖的題。可以通過floyd求最大路徑來解決。

從網上找了一份代碼，驗證了可以使用。

代碼中D[v][w] 是頂點v到頂點w的最大路徑

? ? ? ? ?p[v][w][u]是頂點v到頂點w最大路徑上第u個頂點的序號。

? ? ? ? ?INFINITY 頂點間無邊時的值，是個負數

算法原理是，如果發現v 、w頂點中插入頂點u距離變大，則更新最大路徑和最大距離。

代碼如下：http://blog.csdn.net/cxllyg/article/details/7606599

#include <iostream> #include <string> using namespace std;#define INFINITY -10000 #define MAX_VERTEX_NUM 20 typedef struct MGraph{string vexs[MAX_VERTEX_NUM];//頂點信息，這里就是要處理的字符串，每個字符串看做一個頂點int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣，符合條件的兩個字符串之間有邊int vexnum, arcnum;//頂點數就是字符串的個數 }MGraph;void CreateDG(MGraph &G)//構造有向圖 {int i, j;int m;cout<<"請輸入要處理的字符串個數：";cin>>G.vexnum;cout<<"請輸入這"<<G.vexnum<<"個字符串：";for(i=0; i<G.vexnum; i++)cin>>G.vexs[i];cout<<"請輸入m：";cin>>m;for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++){if(G.vexs[i].substr(G.vexs[i].size()-m,m)==G.vexs[j].substr(0,m))//根據前后m個字符是否匹配確定兩字符串之間是否有邊G.arcs[i][j]=1;elseG.arcs[i][j]=INFINITY;} }//利用弗洛伊德算法求各頂點間的最長路徑，p保存路徑，D保存各頂點間的最長路徑，如果出現循環，函數返回false，反之返回true bool Largeset_FLOYD(MGraph G, int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM], int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM]) {int v, w, u;int i, j;for(v=0; v<G.vexnum; v++)for(w=0; w<G.vexnum; w++){D[v][w]=G.arcs[v][w];for(u=0; u<G.vexnum; u++)p[v][w][u]=-1;if(D[v][w]>INFINITY){p[v][w][0]=v;p[v][w][1]=w;}}for(u=0; u<G.vexnum; u++)for(v=0; v<G.vexnum; v++)for(w=0; w<G.vexnum; w++){if(D[v][u]>INFINITY && D[u][w]>INFINITY && D[v][u]+D[u][w]>D[v][w] )//改進的弗洛伊德算法，求最長路徑 {D[v][w]=D[v][u]+D[u][w];//更新p，以便打印路徑for(i=0; i<G.vexnum; i++){if(p[v][u][i]!=-1)p[v][w][i]=p[v][u][i];elsebreak;}for(j=1; j<G.vexnum; j++){if(p[u][w][j]!=-1)p[v][w][i++]=p[u][w][j];elsebreak;}}}//判斷是否有循環for(v=0; v<G.vexnum; v++)if(D[v][v]!=INFINITY)return false;return true; }void main() {int i, j;int posx, posy;MGraph g;CreateDG(g);int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];bool flag=true;flag=Largeset_FLOYD(g, p, D);/* for(i=0; i<g.vexnum; i++){for(j=0; j<g.vexnum; j++)cout<<D[i][j]<<" ";cout<<endl;}*/if(flag){cout<<"最大長度為：";int max=-10000;for(i=0; i<g.vexnum; i++)for(j=0; j<g.vexnum; j++){if(D[i][j]>max){max=D[i][j];posx=i;posy=j;}}cout<<max<<endl;cout<<"字符串鏈為：";for(i=0; i<g.vexnum; i++)//打印字符串鏈 {if(p[posx][posy][i]!=-1)cout<<g.vexs[p[posx][posy][i]]<<" ";}cout<<endl;}elsecout<<"錯誤：出現循環"<<endl;system("pause");}

?

轉載于:https://www.cnblogs.com/dplearning/p/3985086.html

總結

以上是生活随笔為你收集整理的【编程题目】有 n 个长为 m+1 的字符串，如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配......的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。