37.
有n个长为m+1的字符串,
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配,则两个字符串可以联接,
问这n个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。
这题代码和网上的一样。抄的。即使是别人的,也要自己手打。不要放弃
#include<iostream> #include<stdio.h> #include<cstring> #include<assert.h> using namespace std; #define INFINITY -10000 #define MAX_VERTEX_NUM 20 //太大小心爆 struct graph{ string vexs[MAX_VERTEX_NUM];//顶点,每个字符串就是一个顶点 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵,符合条件的两个字符串之间有边 int vexnum,arcnum;//顶点数 }; void creatGraph(graph &g){//构造有向图 int i,j,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; else g.arcs[i][j]=INFINITY;//没边,我们认为到达不了 } } //利用弗洛伊德求各顶点之间最长的路径,p保存路径,d保存最长路径,如果出现循环,返回false bool floyd(graph g,int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],int d[MAX_VERTEX_NUM][MAX_VERTEX_NUM]){ int v,w,u,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,以便打印路径 //这是干嘛?这是告诉我们顶点v到m走过了那些顶点 for(i=0;i<g.vexnum;i++){ if(p[v][u][i]!=-1) p[v][w][i]=p[v][u][i]; else break; } for(j=1;j<g.vexnum; j++){ if(p[u][w][j]!=-1) p[v][w][i++]=p[u][w][j]; else break; } } } //判断是否有循环 //如果自己到自己不是负无穷,说明能走到,说明有环 for(v=0;v<g.vexnum;v++) if(d[v][v]!=INFINITY) return false; return true; } int main(){ int i,j; int posx,posy; graph g; creatGraph(g); int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int d[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; bool flag=true; flag=floyd(g,p,d); 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; } else cout<<"错误:出现循环"<<endl; return 0; }