/*37.（字符串）有 n 个长为 m+1 的字符串，如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配，则两个字符串可以联接，问这 n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。start time = 18:27end 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;    else        return 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;}