P1019 [NOIP2000 提高组] 单词接龙刷题笔记

P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路来自大佬 Chardo 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

匹配：

将第一个字符串末尾和第二个字符串第一个开始匹配

如果 j<i这段走完了

flag还没被修改说明已经存在重叠部分

可以连接

反之如果匹配不成功

将第一个字符串的指向往左移动一位再和第二个串开头字符看是否匹配

如果i=3,j=3说明有一段长度为3的串匹配成功了可以返回长度3了

#include<iostream>
#include<string.h>
using namespace std;
string str[20];
int use[20];
int n,ans;
int clink(string x,string y){

   for(int i=1;i<min(x.length() ,y.length());i++ ){
       int flag=1;
       for(int j=0;j<i;j++){
           if(x[x.length() -i+j]!=y[j]){
               flag=0;
           }
       }
       if(flag){
           return i;
       }

   }
   return 0;

}
void slove(string nowstr ,int nowlen){
   ans=max(ans,nowlen);
   for(int i=0;i<n;i++){
       if(use[i]>=2){
           continue;
       }
       int c=clink(nowstr,str[i]);
       if(c>0){
           use[i]++;
           slove(str[i],nowlen+str[i].length() -c);
           use[i]--;
       }
   }

}
int main(){

   cin>>n;
   for(int i=0;i<n;i++){
       cin>>str[i];
   }
   cin>>str[n];
   slove(' '+str[n],1);
   cout<<ans;

   return 0;
}