D. World of Mouth

Codeforces

IDCF100D

Time5000ms

Memory256MB

Difficulty—

strings

English · Original

Chinese · Translation

Formal · Original

There are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made. She asked _n_ of her friends to help her. They all formed a circle and Aida told the person to her right a piece of news which was just a simple string. Then each person told the string to the person on his/her right. But they didn't tell the string exactly as they'd heard it. Each person made at most one of these two types of changes: * Removing one character from the end of the heard string. * Adding a character to the end of the heard string. Finally when the rumor passed exactly _n_ moves (a complete cycle), Aida heard something quite different from what she expected from the person on her left. She thinks someone has cheated and made some changes other than those explained above. Now she wants you to write a Pike piece of code which gets the initial and final strings and tells Aida whether it's possible to get to the final string from the initial one, by the rules described above. ## Input The first line contains a single integer _n_ (2 ≤ _n_ ≤ 8 × 106), the number of Aida's friends. The following two lines contain a non-empty string each — initial and final strings. The lengths of strings are at most 107 and they only contain English alphabet letters. ## Output Write a single _YES_ or _NO_. Write _YES_ only if it's possible to get to the final string from the initial string. [samples] ## Note The input is case-sensitive, while the output is not.

如今媒体上充斥着大量谣言。有一天，Aida 决定探究谣言是如何产生的。她请了 #cf_span[n] 位朋友帮忙。他们围成一个圈，Aida 将一条仅由简单字符串组成的消息告诉了她右边的人。然后每个人都将听到的字符串传给右边的人。但他们并没有完全按照听到的内容传递：每个人最多进行以下两种操作之一：当谣言恰好经过 #cf_span[n] 次传递（完成一圈）后，Aida 从她左边的人那里听到了与她预期完全不同的内容。她认为有人作弊，进行了上述规则之外的更改。现在她希望你编写一段 #cf_span(class=[tex-font-style-underline], body=[Pike]) 代码，接收初始字符串和最终字符串，并判断是否可能根据上述规则从初始字符串得到最终字符串。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 8 × 106])，表示 Aida 的朋友数量。接下来两行各包含一个 #cf_span(class=[tex-font-style-underline], body=[non-empty]) 字符串——初始字符串和最终字符串。字符串长度至多为 #cf_span[107]，且仅包含英文字母。请输出一行 _YES_ 或 _NO_。仅当可以从初始字符串得到最终字符串时输出 _YES_。输入区分大小写，而输出不区分大小写。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 8 × 106])，表示 Aida 的朋友数量。接下来两行各包含一个 #cf_span(class=[tex-font-style-underline], body=[non-empty]) 字符串——初始字符串和最终字符串。字符串长度至多为 #cf_span[107]，且仅包含英文字母。 ## Output 请输出一行 _YES_ 或 _NO_。仅当可以从初始字符串得到最终字符串时输出 _YES_。 [samples] ## Note 输入区分大小写，而输出不区分大小写。

**Definitions** Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 8 \times 10^6 $, be the number of friends. Let $ s, t \in \Sigma^* $ be the initial and final strings, respectively, where $ \Sigma $ is the set of English alphabet letters, and $ 1 \leq |s|, |t| \leq 10^7 $. **Constraints** 1. $ |s| = |t| $ 2. Each of the $ n $ friends performs exactly one transformation: - Either **no change**, or - **One character substitution** (any letter to any other letter). 3. The transformation propagates cyclically: friend $ i $ receives the string from friend $ i-1 $ (mod $ n $) and passes the transformed version to friend $ i+1 $ (mod $ n $), for $ i = 1, \dots, n $. 4. The total number of substitutions across all friends is at most $ n $. **Objective** Determine whether there exists a sequence of $ n $ transformations (each being identity or single-character substitution) such that, after one full cyclic pass, the initial string $ s $ becomes the final string $ t $. Output "YES" if possible, "NO" otherwise.

Samples

Input #1

100
Codeforces
MMIODPC

Output #1

Yes

Input #2

5
MMIOD
CF

Output #2

No

API Response (JSON)

{
  "problem": {
    "name": "D. World of Mouth",
    "description": {
      "content": "There are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made. She asked _n_ of her friends to help her. They all formed a circle and Aida told the person to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF100D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made.\n\nShe asked _n_ of her friends to help her. They all formed a circle and Aida told the person to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "如今媒体上充斥着大量谣言。有一天，Aida 决定探究谣言是如何产生的。\n\n她请了 #cf_span[n] 位朋友帮忙。他们围成一个圈，Aida 将一条仅由简单字符串组成的消息告诉了她右边的人。然后每个人都将听到的字符串传给右边的人。但他们并没有完全按照听到的内容传递：每个人最多进行以下两种操作之一：\n\n当谣言恰好经过 #cf_span[n] 次传递（完成一圈）后，Aida 从她左边的人那里听到了与...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 8 \\times 10^6 $, be the number of friends.  \nLet $ s, t \\in \\Sigma^* $ be the initial and final strings, respectively, where $ \\Sigma $ is t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments