[语言月赛 202406] 通配符匹配

Luogu

IDLGB3990

Time1000ms

Memory512MB

DifficultyP2

2024O2优化字符串（入门）语言月赛

给定两个字符串 $s, t$，规定 $s(l, r)$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符组成的字符串（$1 \leq l \leq r \leq |s|$）。例如：若 $s = \texttt{luogu}$，则 $s(2,4) = \texttt{uog}$。现在，请你求出所有的 $l, r$，使得 $t$ 和 $s(l, r)$ 匹配。 ## Input 第一行是一个字符串 $s$。第二行是一个字符串 $t$。 ## Output 输出若干行，每行两个整数，表示一组 $l,r$。按 $l$ 从小到大的顺序输出。可以证明，按这个顺序进行输出的方案是唯一的。 [samples] ## Background 我们称两个字符 $a,b$ 是**匹配**的，当且仅当 $a =b$ 或 $a,b$ 中至少一个是字符 $\texttt ?$（ASCII 值 $63$）。例如： - $\texttt x$ 和 $\texttt x$ 是匹配的； - $\texttt x$ 和 $\texttt ?$ 是匹配的； - $\texttt ?$ 和 $\texttt x$ 是匹配的； - $\texttt ?$ 和 $\texttt ?$ 是匹配的； - 但 $\texttt x$ 和 $\texttt y$ **不是**匹配的。我们称两个字符串 $s$ 和 $t$ 是匹配的，当且仅当 $s$ 和 $t$ 长度相同，且对应位置上的字符是匹配的。例如，$\texttt{abc??z}$ 和 $\texttt{a?cx??}$ 是匹配的。 ## Note ### 数据规模与约定以下用 $n$ 表示字符串 $s, t$ 的长度上限。 | 测试点编号 | $n \leq$ | 特殊约定 | | :-: | :-: | :-: | | $1, 2$ | $1$ | 无 | | $3$ | $300$ | A | | $4$ | $300$ | B | | $5$ | $300$ | C | | $6$ | $300$ | 无 | | $7$ | $10^3$ | A | | $8$ | $10^3$ | B | | $9$ | $10^3$ | C | | $10$ | $10^3$ | 无 | 对全部的测试数据，保证 $1 \leq n \leq 10^3$，$|t|\le |s|$，$s, t$ 中只含小写英文字母和字符 $\texttt ?$（英文半角，ASCII 为值 $63$）。特殊性质表： | 代号 | $s$ 中含有 $\texttt{?}$ | $t$ 中含有 $\texttt{?}$ | | :-: | :-: | :-: | | A | $\times$ | $\times$ | | B | $\checkmark$ | $\times$ | | C | $\times$ | $\checkmark$ |

Samples

Input #1

luogu
uog

Output #1

2 4

Input #2

aabbcc
b??

Output #2

3 5
4 6

Input #3

a?b?c?
bcc

Output #3

3 5
4 6

Input #4

a?b?c?
b??

Output #4

2 4
3 5
4 6

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202406] 通配符匹配",
    "description": {
      "content": "给定两个字符串 $s, t$，规定 $s(l, r)$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符组成的字符串（$1 \\leq l \\leq r \\leq |s|$）。例如：若 $s = \\texttt{luogu}$，则 $s(2,4) = \\texttt{uog}$。 现在，请你求出所有的 $l, r$，使得 $t$ 和 $s(l, r)$ 匹配。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3990"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定两个字符串 $s, t$，规定 $s(l, r)$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符组成的字符串（$1 \\leq l \\leq r \\leq |s|$）。例如：若 $s = \\texttt{luogu}$，则 $s(2,4) = \\texttt{uog}$。\n\n现在，请你求出所有的 $l, r$，使得 $t$ 和 $s(l, r)$ 匹配。\n\n## Input\n\n第一行是...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments