luogu P1019 单词接龙

解析

一道dfs题，但是坑在题意不清，实际是求最短重叠词段，我一开始求成了最长的（直接增大了难度…）。
主要就是两个部分，dfs和concate，dfs遍历构造出来的搜索树，concate计算重叠长。
tips: 为什么这是道搜索题？答：以一个词开始（根节点），依次考虑数组中的词能否连接（分支），算最长词长。

---

代码

修改了一下，比较简练了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int n,max_len = 0;
vector<string> cot(21);
int times[21];
int concate(string &a, string &b){
    int clen = 0,bar_len = min(a.size(),b.size()) ;
    int a_i,b_i,cur_len;
    a_i = a.size() - 1;
    b_i = 0;
    cur_len = 1;
    for(int i=0;i<bar_len;i++){
        if( a.compare(a_i,cur_len,b,b_i,cur_len)==0 ){// ==0 means equal
            clen = cur_len;
            break;
        }
        a_i--;
        cur_len++;
    }
    if(clen == bar_len) return 0; 
    else return clen;
}
void dfs(string str, int len){
    int num;
    len+= str.size();

    if(len>max_len) max_len = len;
    for(int i = 0;i<n;i++){
        if( (num = concate(str,cot[i]))!=0  && times[i]!=2){
            len+= (-num) ;
            times[i]++;
            dfs(cot[i],len);
            len-= ( -num);
            times[i]--;
        }
    } 
}
int main(){

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>cot[i];
    }
    char str;
    cin>>str;

    int num;
    for(int i=0;i<n;i++){
        if(cot[i][0] == str){
            times[i]++;
            dfs(cot[i],0);
            times[i]--;
        }
    }
    cout<<max_len<<endl;
    return 0;
}