题解|2024.3.17西山居笔试第二题

题目描述: 给一个长字符串，和若干小字符串，问选哪几个小字符串可以拼成大串

数据范围：保证有且仅有唯一解，没给数据范围，我猜的暴力能过,胡乱写写过了

题目思路：开个map，往下搜一下

笔试感受：总体感觉比米哈游简单，题少问的简单点还行

#include<bits/stdc++.h>
using namespace std;
/*
测试数据
abcefdegh
5
abc efdeg efde gh ss
*/
map<string,int> mm;
vector<int> ans;
bool flag=0;
void dfs(string s,vector<int> t){
	if(flag) return ;
	if(s==""){ 
             //因为用了erase是会删没的，唯一解找到直接返回就行了
		ans=t;
		flag=1;
		return ;
	}
	string k="";
	for(int i=0;i<(int)s.size();i++){
		k+=s[i];
		if(mm.count(k)){
			vector<int> next=t;
			string tmp=s;
			next.push_back(mm[k]);
			tmp.erase(0,i+1);  //这里感觉可以传个下标下去，当时想着随便写写
			dfs(tmp,next);
		}
	}
}
int main(){
	string str;
	vector<string> s;
	int n;
	cin>>str;
	cin>>n;
	for(int i=0;i<n;i++){
		string tmp;
		cin>>tmp;
		s.push_back(tmp);
		mm[tmp]=i;
    }
    vector<int> k;
	dfs(str,k);
	for(auto t:ans) cout<<t<<" ";
	cout<<endl;
	return 0;
}

#西山居#