C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 612K, 提交时间: 2020-05-06 14:25:40

#include<bits/stdc++.h>
using namespace std;
int n,ans=0,vis[20]={0};
string s[20],t;
void dfs(string a){
    int len1=a.size();
    ans=max(ans,len1);
    for(int i=0;i<n;i++){
        int len2=s[i].size();
        if(vis[i]==2) continue;
        for(int j=1;j<min(len1+1,len2);j++){
            if(!s[i].find(a.substr(len1-j,j))){
                vis[i]++;
                dfs(a+s[i].substr(j,len2-j));
                vis[i]--;
                break;
            }
        }
    }
}
main()
{
   cin>>n;
   for(int i=0;i<n;i++) cin>>s[i];
   cin>>t;
   dfs(t);
   cout<<ans;
}

C++(g++ 7.5.0) 解法, 执行用时: 246ms, 内存消耗: 432K, 提交时间: 2023-06-07 16:29:51

#include <bits/stdc++.h>
using namespace std;
string a[30];
int n,mx; 
int bk[30];
int pt(string a,string b){
	for(int i=1;i<=min(a.size(),b.size());i++){
		int f=1;
		for(int j=0;j<i;j++){
			if(b[j]!=a[a.size()-i+j]) f=0;
		}
		
		if(f)return i;
	}
	return 0;
} 
void dfs(string s,int sum){
	mx=max(mx,sum);
	for(int i=0;i<n;i++){
		if(bk[i]>=2)continue;
		int t=pt(s,a[i]);
		if(t){
			bk[i]++;
			dfs(a[i],sum+a[i].size()-t);
			bk[i]--;
		}
	}
}
int main(){
	string st;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	cin>>st;
	dfs(st,1);
	cout<<mx; 
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 484K, 提交时间: 2019-10-09 21:30:13

#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
int n,ans,vis[25]; string s[25],t;
void dfs(string a){
	int la=a.length(); ans=max(ans,la);
	rep(i,0,n){
		if(vis[i]==2) continue;
		int ls=s[i].length();
		rep(j,1,min(ls,la+1))
			if(!s[i].find(a.substr(la-j,j))){
				vis[i]++;
				dfs(a+s[i].substr(j,ls-j));
				vis[i]--; break;
			}
	}
}
int main(){
	cin>>n; rep(i,0,n) cin>>s[i];
	cin>>t; dfs(t); cout<<ans<<'\n';
}