网站建设优化服务市场,做网站要不要签合同,企业品牌网站建设方案,建设网站学什么语言算法提高之单词接龙 核心思想#xff1a;dfs 预处理每两个字符串之间最短的公共部分长度 求最短公共 最终字符串是最长 dfs所有开头字符串 #include iostream#include cstring#include algorithmusing namespace std;const int N 25;int g[N][N…算法提高之单词接龙 核心思想dfs 预处理每两个字符串之间最短的公共部分长度 求最短公共 最终字符串是最长 dfs所有开头字符串 #include iostream#include cstring#include algorithmusing namespace std;const int N 25;int g[N][N];int n;string word[N];int used[N];int ans;void dfs(string dragon,int last){ans max((int)dragon.size(),ans);used[last] ;for(int i0;in;i){if(g[last][i] used[i] 2) //last和i有公共部分{dfs(dragonword[i].substr(g[last][i]),i);}}used[last]--; //回溯}int main(){cinn;for(int i0;in;i) cinword[i];char start;cinstart;for(int i0;in;i) //预处理每两个字符串之间最短的公共部分长度{for(int j0;jn;j){string a word[i],bword[j];for(int k1;kmin(a.size(),b.size());k){if(a.substr(a.size()-k) b.substr(0,k)){g[i][j] k;break;}}}}for(int i0;in;i)if(word[i][0] start) //可以开头dfs(word[i],i);coutansendl;}
