当前位置:网站首页>P1019 word Solitaire (DFS & string matching)

P1019 word Solitaire (DFS & string matching)

2021-08-10 08:03:56 wx6110fa547fd20

P1019 The word chain (DFS& string matching )

  Subject portal

The question : Give me some words ( Use it twice at most ) Word Solitaire ( The suffix of the former word coincides with the prefix of the latter word ( Less than the length of the word ), Find the maximum length .

Ideas : Write a matching pre suffix function , Reuse DFS Just search .

#include<bits/stdc++.h>
using namespace std;
string b[25];
int n,ans,vis[25];
int fun(string a,string b){ // word a Suffixes and b Prefix matching  
	int la=a.size(),lb=b.size(),f=1;
	for(int i=1;i<min(la,lb);i++,f=1){
		for(int j=0;j<i;j++)
			if(a[la-i+j]!=b[j]){
				f=0;
			}
		if(f) return i;
	}
	return 0;
}
void dfs(string a,int la){ 
	//cout<<"a="<<a<<" "<<"la="<<la<<endl;
	ans=max(ans,la);
	for(int i=0;i<n;i++){
		if(vis[i]>=2) continue;
		int len=fun(a,b[i]),lb=b[i].size();
		if(len){
			vis[i]++;
			dfs(b[i],la+lb-len);
			vis[i]--;
		} 
	}	
}
int main(){
	cin>>n;
	for(int i=0;i<=n;i++) cin>>b[i];
	dfs(' '+b[n],1);// Make sure the first word matches  
	cout<<ans<<endl;
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810080205517m.html

随机推荐