#1701. DNA的转录

DNA的转录

背景

在分子生物学中,基因表达的第一步是转录。在此过程中,以DNA的一条链(模板链)为模板,合成一条与之互补的信使RNA(mRNA) 链。DNA和RNA都使用碱基编码遗传信息,但它们的碱基组成略有不同:

  • DNA碱基:A A (腺嘌呤), TT (胸腺嘧啶),C C (胞嘧啶), GG (鸟嘌呤)
  • RNA碱基: A A (腺嘌呤), U U (尿嘧啶), C C (胞嘧啶), G G (鸟嘌呤)
  • 转录时,碱基的互补配对规则如下:
  1. DNA模板链上的 A A 对应 RNA 上的 U U
  2. DNA模板链上的 T T 对应 RNA 上的 A A
  3. DNA模板链上的 C C 对应 RNA 上的 G G
  4. DNA模板链上的 G G 对应 RNA 上的 C C

题干描述

给你一个mRNA的序列,DNA的一条链(模板链)序列,判断这个mRNA是否可能由此DNA(模板链)转录而来(能互补配对)。 注意:

  1. 输入的mRNA序列方向与输入的DNA模板链方向相同(通常理解为都为55'端到33'端方向,由于转录时互补配对,mRNA的33'端对应DNA的55'端),所以你需要先反转mRNA序列
  2. 题目中给出的DNA序列是模板链(Template Strand)。

格式说明

输入

  • 第一行输入两个整数n,m(1mn500) n,m ( 1 \le m \le n\le 500 )
  • 第二行输入nn个字符,为解旋后的DNA模板链序列。
  • 第三行输入mm个字符,为mRNA 序列。

输出

“YES”或“NO”

样例说明

30 6
ATCGCCGTAAGTAACGGTTTTAAATAGGCC
AACCGU
YES

说明:该mRNA可能由此DNA模板链的ACGGTTACGGTT片段转录而来。

限制条件

1s, 512miB 每次测试.