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