首页 > 试题广场 >

实现字通配符*

[编程题]实现字通配符*
  • 热度指数：5981 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}在 Linux Shell 中，通配符 `*` 代表任意长度（可为 0）的字符串。给定：
\hspace{23pt}\bullet\, 一条模式串 `p`（仅包含可见字符及通配符 `*`，无其他元字符）；
\hspace{23pt}\bullet\, 一条目标串 `s`；
\hspace{15pt}请输出 `s` 中所有与 `p` 匹配的子串的起始位置（从 0 开始计）及长度。

\hspace{15pt}若不存在匹配，输出 `-1 0`。多组匹配按"起始位置升序，长度升序"排序输出。

\hspace{15pt}> `*` 可匹配空串；匹配不要求整个 `s`，只需匹配其任一连续子串。

输入描述:
\hspace{15pt}第一行：模式串 `p` 
\hspace{15pt}第二行：目标串 `s`


输出描述:
\hspace{15pt}对每一个匹配子串输出 `匹配起始位置  匹配的长度`（空格分隔）一行；若无匹配输出 `-1 0`。
示例1

输入

shopee*.com
shopeemobile.com

输出

0 16

说明

0 起始位置，16长度
示例2

输入

*.com
shopeemobile.com

输出

0 16
1 15
2 14
3 13
4 12
5 11
6 10
7 9
8 8
9 7
10 6
11 5
12 4
示例3

输入

o*m
shopeemobile.com

输出

2 5
2 14
7 9
14 2
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-28 16:50:33
解题思路 这是一道关于通配符匹配的问题，主要思路如下： 使用DFS（深度优先搜索）来实现通配符'*'的匹配 ''可以匹配0个或多个字符，因此在遇到''时有三种选择： 不匹配任何字符，继续匹配下一个模式字符 匹配当前字符，保持在当前模式字符 匹配当前字符，继续匹配下一个模式字符 使用 set 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 测试工程师 PHP工程师 哈希 查找 虾皮信息 2019 Java工程师
来自：Shopee 2019...
上传者：小小
难度：
21条回答 19680浏览

热门推荐

通过挑战的用户

查看代码

相关试题

实现字通配符*

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号