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

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

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

匹配 ：

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

如果 j<i这段走完了

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

可以连接

反之 如果匹配不成功

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

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

#include
#include
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<
return 0;
}