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;
}?