【编程题目】有 n 个长为 m+1 的字符串，如果某个字符串的最后 m 个字符与某个字符串的前 m 个字符匹配...

/*
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;
    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;
}