[cf] Codeforces Round #527 (Div. 3) C. Prefixes and Suffixes 字符串,前缀后缀,枚举

前言

t a g : tag : tag:字符串 前缀,后缀 传送门 :

题意

给定一个 n n n,表示未知串的长度

然后给定 2 ∗ n − 2 2*n-2 2∗n−2组字符串,这些字符串可能是该未知串的前缀或者后缀

询问这些字符串是前缀还是后缀

数据范围 : n ∈ ( 1 , 00 ] n\in(1,00] n∈(1,00]

思路

因为数据范围很小,我们可以考虑暴力

首先枚举 a [ i ] a[i] a[i],然后我们再枚举长度为 n − a [ i ] . s i z e ( ) n-a[i].size() n−a[i].size()的串

如果存在,我们就将其进行拼接,然后暴力 c h e c k check check

c h e c k check check过程就是看是否所有串都满足要么是前缀否则就是后缀这种操作

最后输出即可

Code

// Problem: C. Prefixes and Suffixes
// Contest: Codeforces - Codeforces Round #527 (Div. 3)
// URL: https://codeforces.com/contest/1092/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 410;
string s[N];
int i,j;
int n;

bool check(string t){
	
	//判断是否合法
	Fup(i,1,n*2-2){
		string pre = t.substr(0,s[i].size());
		string suf = t.substr(n-s[i].size());
		if(s[i]!=pre && s[i]!=suf) return false;
	}
	
	Fup(i,1,n*2-2){
		string pre = t.substr(0,s[i].size());
		string suf = t.substr(n-s[i].size());
		
		if(s[i] == pre && s[i] == suf){
			if(mp[s[i]]) cout