首页 > 试题广场 >

实现字通配符*

[编程题]实现字通配符*
  • 热度指数：6675 时间限制：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
算法知识视频讲解
添加回答
Python
snhl0413头像 snhl0413 
# 将一楼的大佬的代码改写成了Python， all pass， 感谢
import sys
def DFS(i,j): 
    if j==len(t):
        S.add(i)
        return
    if i==len(s):
        return
    if s[i]==t[j]:
        DFS(i+1, j+1)
    elif t[j]=='*':
        DFS(i, j+1)
        DFS(i+1, j)
        DFS(i+1, j+1)
    return
while True:
    line = sys.stdin.readline().strip()
    if line == '':
        break
    t = line
    s = input()
    S = set()
    flag = False
    for i in range(len(s)):
        # i is the start idx of s
        # S includes all the end index it that s[i:it] matches t
        if s[i]==t[0] or t[0]=='*':
            DFS(i, 0)
        if len(S) != 0:
            flag = True
            for it in sorted(S):
                if it>i:
                    print(i,it-i)
        S.clear()
    if not flag:
        print(-1, 0)


编辑于 2020-03-14 00:27:20 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

实现字通配符*

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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