P8983 - li<x>nk with Centrally Symmetric Strings

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：Special Judge 上传者：

提交：0 通过：0

Given a string, determine if it can be represented as the concatenation of several centrally symmetric substrings.

Formally, a string

S

is centrally symmetric if and only if it satisfies one of the following conditions:

$S$ is an empty string.
$S = o ∣ s ∣ x ∣ z$ , i.e., $S$ is one of the four letters: o, s, x and z.
$S = b Sq ∣ d S p ∣ p S d ∣ qS b ∣ n S u ∣ u S n ∣ o S o ∣ s S s ∣ x S x ∣ zSz$ , i.e., $S$ starts and ends with a pair of centrally symmetric letters, and the middle part is also a centrally symmetric substring.

A string

S

is considered good if and only if there exists an integer

\geq 1

such that

T_1T_2 \cdots T_n

, where

T_i

(

\le i \le n

) is a centrally symmetric substring.

Given a string

S

, determine whether it is a good string.

The input contains multiple test cases.
The first line contains an integer

\leq T \leq 10^6)

, indicating the number of test cases.
The following

T

lines each contain a string

S

(

\leq |S| \leq 10^6

) consisting of lowercase English letters, representing the string to be tested.
It is guaranteed that

∑∣S∣≤5×106\sum |S| \leq 5 \times 10^6

, where

∣ S ∣

represents the length of string

S

For each test case, if the string is good, output “Yes”; otherwise, output “No”.

You can output each letter in any case (lowercase or uppercase). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be accepted as a positive answer.

3
sosos
hahaha
sbzzq

Yes
No
Yes

For the third test case, the string can be divided into two substrings, “s” and “bzzq”, both of which are centrally symmetric substrings. Therefore, the output is “Yes”.

2023牛客多校2

8983: link with Centrally Symmetric Strings

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签