单词接龙(字符串+搜索)

传送门

题意:给你n个字符串和一个字符,每个字符串最多使用两次,通过两字符串首尾相接,求出以该字符开头的最长的字符串.

分析:基本思路是搜索,这个应该不难看出.难点在于对于很多细节的处理,比如"龙"与单词的重叠部分的处理等等.

int n,ans,used[21];
string start,word[21];
//判断我当前要接到"龙"尾的单词:
//该单词的"头"与"龙"的尾能够重合(即相同)的长度
bool check(string s,string ss,int k){
    int len=s.size();
    for(int i=0;i<k;i++)
    	if(s[len-k+i]!=ss[i])return false;
    return true;
}
//拼接操作
void add(string &s,string ss,int k){
    int len=ss.size();
    for(int i=k;i<len;i++)
    	s+=ss[i];
}	
void dfs(string now){//now表示已经连接起来的"龙"
    int len=now.size();//len当前"龙"的长度
    ans=max(ans,len);//更新答案
    for(int i=1;i<=n;i++){
    	if(used[i]==2)continue;//最多用两次
    	int k=word[i].size();//单词长度
    	for(int j=k;j>=1;j--){
//长度从大到小判断能否相接,这里有人说长度应该从小到大枚举,接得越少越好
//但是拼接的前提不应该是保证能接的完全接上吗?(洛谷数据太水,两种写法都能过)
//check当前的"龙"now,与枚举到的单词word[i],
//是否头尾j位是相同的,
        	if(check(now,word[i],j)){
        		string temp=now;
        		add(temp,word[i],j);//接起来
        		if(temp==now)continue;
//接上该单词后,"龙"的长度不变,根据最优性原理,没必要
        		used[i]++;
//如果可以接上,该单词使用次数加1
        		dfs(temp);//继续搜下去
        		used[i]--;//回溯
        	}
    	}
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>word[i];//读入n个单词
    cin>>start;//读入"龙"头
    dfs(start);//直接从"龙"头开始搜索
    cout<<ans<<endl;
    return 0;
}

总结:有关字符串的搜索题,思维难度不会很大,就是要细心,细节特别多,坑特别多.