1018 单词接龙（搜索字符串处理）

骑猪看日落 2022-06-18 09:18 161阅读 0赞

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

touch

cheat

choose

tact

样例输出 Sample Output

数据范围及提示 Data Size & Hint

（连成的“龙”为atoucheatactactouchoose）

写了整整一上午。。。

搜索部分就是盲目的搜索就行，主要是字符串拼接的时候，abab 和ababc 连接的时候是abababc

代码：

#include<iostream>
    #include<string>
    #include<string.h>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    char str[25][100],ss[150];
    int n,v[25]={0},Max=0,MAX=-1;
    int check(int x)
    {
    	int i,j,k,r,t,flag=0,len;
    	len = strlen(ss);
    	while (len > 0)
    	{
    		len--;
    		for (i=len,j=0; ss[i]&&str[x][j]; i++,j++) //向前比较 
    		{
    			if (ss[i] != str[x][j])
    			 break;
    		}
    		if (ss[i]=='\0')
    		{
    			return len;
    			break;
    		}
    	}
    	 return 0;
    }
    void dfs()
    {
    	int c,i;
    	char t[100];
    	if (strlen(ss) > Max)
    	{
    		Max = strlen(ss);
    	//	cout<<ss<<Max<<endl;
    	}
    	for (i=0; i<n; i++)
    	{
    		if (v[i]<2)
    		{
    			if (c = check(i))//返回为真说明已经将str[i]连接到 新串 ss中 
    			{
    				v[i]++; //记录一次
    				strcpy(t,ss);
    				ss[c]='\0';
    				strcat(ss,str[i]);
    				dfs();
    				strcpy(ss,t);
    				v[i]--;
    			}
    		}
    	}
    }
    int main()
    {
    	int i,j;
    	char ch;
    	cin>>n;
    	for (i=0; i<n; i++)
    	{
    		cin>>str[i];
    	}
    	cin>>ch;
    	for (i=0; i<n; i++)
    	{
    		if (str[i][0] != ch)
    		 continue;
    		//找到以ch打头的字符串，让它作为新的串的头 
    		strcpy(ss,str[i]);
    		memset(v,0,sizeof(v)); 
    		v[i]++;//记录使用了一次
    		Max=0; 
    		dfs(); 
    		if (Max > MAX)//取最大长度 
    		 MAX = Max;
    	}
    	cout<<MAX;
    	return 0;
    }