QOJ.ac

QOJ

Límite de tiempo: 1.0 s Límite de memoria: 512 MB Puntuación total: 100 Hackeable ✓

#10898. 字符串新手

Estadísticas

Chenjb 正在钻研字符串理论。他试图解决一个字符串问题。在该问题中,给定两个非空字符串 $S$ 和 $T$,你需要报告字符串 $S$ 中与 $T$ 匹配的子串数量。例如,$S = \text{“ababac”}$,$T = \text{“aba”}$,答案为 2,因为 $T$ 在 $S$ 中出现了两次:$\text{“[aba]bac”}$ 和 $\text{“ab[aba]c”}$。

Chenjb 是一名程序设计竞赛的新手。设数组 $S[1..n]$ 表示长度为 $n$ 的字符串 $S$,设数组 $T[1..m]$ 表示长度为 $m$ 的字符串 $T$。Chenjb 使用直观的贪心策略写下了以下 C/C++ 代码:

int Find_Answer () {
    int j = 1, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (S[i] != T[j]) j = 1;
        if (S[i] == T[j]) j++;
        if (j > m) {
            ans++;
            j = 1;
        }
    }
    return ans;
}

Chenjb 提交了他的代码,幸运的是,它通过了。但 Chenjb 很快意识到他的贪心算法并不总是正确的。例如,$S = \text{“aaaa”}$,$T = \text{“aaa”}$,正确答案应为 2,但 Chenjb 的代码将返回 1。

你知道,Chenjb 是个新手,所以他向你寻求帮助。给定模板字符串 $T$,你的任务是确定是否存在一个非空字符串 $S$,使得 Chenjb 的代码无法得出正确结果。

输入格式

输入仅包含一组测试数据。 第一行包含一个整数 $m$ ($1 \le m \le 100\,000$),表示模板字符串 $T$ 的长度。 第二行包含一个由 $m$ 个小写英文字母组成的字符串 $T$。

输出格式

如果存在一个非空字符串 $S$ 使得 Chenjb 的代码无法得出正确结果,输出 “Wrong Answer”,否则输出 “Correct”。

样例

样例输入 1

3
abc

样例输出 1

Correct

样例输入 2

3
aaa

样例输出 2

Wrong Answer

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.