首页 > 试题广场 >

实现字通配符*

[编程题]实现字通配符*
  • 热度指数：5819 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
在Linux Shell命令下通配符'*'表示0个或多个字符, 现编写一段代码实现通配符'*'的功能，注意只需要实现'*', 不用实现其他通配符。

输入描述:
第一行输入通配字符串
第二行输入要匹配查找的字符串


输出描述:
输出所有匹配的字串起始位置和长度，每行一个匹配输出
如果不匹配，则输出 -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条回答 17759浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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