首页 > 试题广场 >

实现字通配符*

[编程题]实现字通配符*
  • 热度指数：7281 时间限制：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`  （长度不超过20）
\hspace{15pt}第二行：目标串 `s`  （长度不超过 5\times 10^6）
保证输出的总行数不超过 5\times 10^6。


输出描述:
\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
算法知识视频讲解
添加回答
Python3
tjss666一号头像 tjss666一号
这应该是最简单的方法了，而且非常高效，用时33ms,占用15324KB
在HJ71我们可以学习到match的使用方法，这个地方使用match极大地减少了工作量 
a = input()
panduan = list(a.split('*'))
b = input()
a,c,lenb = a.replace('*','.*'),[],len(b)
for i in range(len(panduan)):
    if not panduan[i] in b:
        print('-1 0')
        quit()
from re import match
for i in range(lenb):
    for j in range(i+1,lenb+1):
        k = b[i:j]
        d = f'{i} {j-i}'
        kd = [k,d]
        c.append(kd)
for i in c:
    pi = match(a,i[0])
    if pi:
        ans = pi.group()
        if ans == i[0]:
            print(i[1])
首先将a以*号分割成为几部分，如果这几部分有任意一部分不在b中，那么就直接输出-1 0并且quit，可以直接跳出整个程序，就没有必要再写else了，然后将a中的*换成一个点加*号，这是很重要的正则表达式，从re中导入match，取出b中所有的连续子串，这个方法是通用必会的，同时，将对应要输出的字符串提前加入到列表中，统一存到列表c中，然后对所有的连续子串，我们使用match去匹配，这里match的返回值有点奇怪，有可能为none，所以必须要使用if条件句，并且使用group去取出最后匹配的值，因为这里已经是分割成所有子串了，所以需要严格匹配子串本身，如果取出的值等于子串本身，我们直接输出之前准备好的字符串即可
发表于 2025-08-14 10:52:51 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 测试工程师 PHP工程师 哈希 查找 深圳虾皮信息科技有限公司 2019 Java工程师
来自：Shopee 2019...
上传者：小小
难度：
1条回答 21510浏览

热门推荐

通过挑战的用户

查看代码

相关试题

实现字通配符*

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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