题目描述：单词接龙

问题描述：单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙" 中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入

输入的第一行为一个单独的整数n(n<=20）表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表来“龙”开头的字母。你可以假定以此字母开头的“龙" 一定存在。

输出

只需输出以此字母开头的最长的“龙”的长度

样例输入

5
at
touch
cheat
choose
tact
a

样例输出

23

思路：
开始的思路是：单词词组变成2倍，直接DFS，进入下一次循环的条件是是否存在相同部分。但是存在的问题是单词变成两倍，会出现解遗漏的问题，同时每次的计算量非常大，时间消耗很大，所以不合适。
后来的思路是：计算每个单词之间相同部分的长度，DFS遍历形成子集树即可。

其中还出现了bug，思路和解都是对的，但是一直WA，后来改了头文件的位置就对了，要把这个文件放在最前面。

// 单词接龙.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

//思路：单词重复出现两次，找当前单词和其他的最大相同部分。
//存在的问题：每个单词只是和后面的单词寻找相同的部分，但是会遗漏和前面单词相同的部分。所以答案有问题。
//存在的问题：即使改了头文件，结果还是WA！
#include
#include
#include
#include
#include
using namespace std;

#define MAX 100
int n, ans, vis[MAX];
string words[MAX];
char ch;

int is_contain(string a, string b, int &con)
{
//cout << "a:" << a << "\tb:" << b << endl; if (b.find(a, ) != string::npos && b != a) //pos-没找到 >=0-找到了
{
//cout << "b contain a" << endl;
return -;
}

int alen = a.length();  
for (int i = ; i < alen; i++) //从第二个字母开始寻找和其他单词相同的部分  
{  
    string temp = a.substr(i);  
    if (b.find(temp, ) ==  && b != temp)  
    {  
        con = alen - i;  
        //cout << "i:" << i << endl;  
        return i;  
    }

}

return -;  

}

void DFS(int index, int cur)
{
if (cur > ans) ans = cur;

for (int i = ; i <  \* n; i++)  
{  
    int con = ;  
    int check = is\_contain(words\[index\], words\[i\], con);  
    //cout << "check:" << check << "\\tcon:" << con << endl;

    if (!vis\[i\] && check >= )  
    {  
        //cout << "a:" << words\[index\] << "\\tb:" << words\[i\] << "\\tcur:" << cur << "\\tres:" << cur + words\[i\].length() - con << endl;  
        vis\[i\] = ;  
        DFS(i, cur + words\[i\].length() - con);  
        vis\[i\] = ;  
    }  
}  

}

int main()
{
while (cin>>n)
{
for (int i = ; i < n; i++) { cin >> words[i];
words[n + i] = words[i];
}
cin >> ch;

    ans = ;  
    memset(vis, , sizeof(vis));  
    for (int i = ; i <  \* n; i++)  
    {  
        if (words\[i\]\[\] == ch)  
        {  
            vis\[i\] = ;  
            DFS(i, words\[i\].length());  
            vis\[i\] = ;  
        }  
    }

    cout << ans << endl;  
}

}

//注意点：头文件写在最前面！！！
//思路：计算每个单词之间的相同部分，然后DFS
//#include
//#include
//#include
//#include
//#include
//using namespace std;
//
//#define MAX 100
//int n, ans, vis[MAX], map[MAX][MAX];
//string words[MAX];
//char ch;
//
//
//int get_length(string a, string b)
//{
// //cout << "=================a:" << a << "\tb:" << b << "==================" << endl; // int a_len = a.length(), b_len = b.length(); // int len = min(a_len, b_len); // for (int i = 0; i < len; i++) // { // string at = a.substr(a_len - i - 1); // string bt = b.substr(0, i + 1); // //cout << "at:" << at << "\tbt:" << bt << endl; // if (at == bt) // { // //cout << "con:" << b.length() - i - 1 << endl; // return b.length() - i - 1; // } // } // // return 0; //} // //void DFS(int index, int cur) //{ // if (cur > ans) ans = cur;
//
// for (int i = 0; i < n; i++) // { // if (vis[i] < 2 && map[index][i]) // { // vis[i] ++; // DFS(i, cur + map[index][i]); // vis[i] --; // } // } //} // //int main() //{ // while (cin>>n)
// {
// for (int i = 0; i < n; i++) // cin >> words[i];
// cin >> ch;
//
// ans = 0;
// memset(vis, 0, sizeof(vis));
// memset(map, 0, sizeof(map));
// for (int i = 0; i < n; i++)
// for (int j = 0; j < n; j++)
// map[i][j] = get_length(words[i], words[j]);
//
// for (int i = 0; i < n; i++)
// {
// if (words[i][0] == ch)
// {
// vis[i] ++;
// DFS(i, words[i].length());
// vis[i] --;
// }
// }
//
// cout << ans << endl;
// }
// return 0;
//}