#227. 魏老板的危机

    ID: 227 Type: Default 1000ms 256MiB Tried: 24 Accepted: 5 Difficulty: 8 Uploaded By: Tags>字符串KMP哈希2024寒假一期结训赛2025暑假二期结训赛

魏老板的危机

Upd1:数据已加强,赛时复杂度错误的代码无法再次通过本题!

Upd2:由于操作系统间换行符差异问题导致评测出锅,现已修复。

Background

DNA,全名脱氧核糖核酸,其基本单元为脱氧核糖核苷酸(下简称核苷酸),由一个磷酸基团、一个五碳糖(脱氧核糖)和一个含氮碱基构成。我们使用含氮碱基标识不同的核苷酸,含氮碱基有4种:A\text{A}(腺嘌呤),C\text{C}(胞嘧啶),G\text{G}(鸟嘌呤),T\text{T}(胸腺嘧啶)。核苷酸通过磷酸二酯键构成双螺旋结构,形成DNA长链,进而孕育了万物的繁衍生息。

为研究方便,本题中我们假定DNA为环形。事实上,仅原核生物具有环形DNA。

Description

某天魏老板逛B站时刷到一个视频,某生命科学科研所公布了人类的某条环状DNA的序列,据说这个位置的DNA序列每种生物都不一样。

于是魏老板测量了自己此段DNA序列,结果魏老板发现其貌似与公布的不一样!?魏老板大惊失色,非常害怕自己不是人类。请验证一下魏老板是否为人类。

Format

Input

输入有两行,为两个字符串 SS 和 $T (1\le |S|,|T|\le 10^6),(S,T\in \set{\text{A},\text{C},\text{G},\text{T}})$,分别表示公布的DNA序列与魏老板的DNA序列。

Output

若验证魏老板是人类,则输出 YES ,否则输出 OHHH!

Samples

ATCAAGCTTCGAAC
AAGCTTCGAACATC
YES
ATCAAGCTTCGAAC
AAGCTTCGAACAGC
OHHH!

P.S.

“我对普通的人类没有兴趣。你们之中要是有外星人、未来人、异世界的人、超能力者,就尽管来找我吧!以上。”