首页 > 试题广场 >

实现字通配符*

[编程题]实现字通配符*
  • 热度指数:7723 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\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`  (长度不超过 10^3


输出描述:
\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

备注:
本题已于下方时间节点更新,请注意题解时效性:
1. 2025-12-25 原数据范围有误,已修正为 10^3,同时重造了数据;时间限制拓展为 2s,空间限制拓展为 256MB。
from sre_constants import JUMP
p = input()
s = input()

star_index = 0
for i in range(0, len(p)):
    if p[i] == "*":
        star_index = i

start = p[:star_index]
stop = p[star_index + 1 :]
# print(start, stop)

A = []
for i in range(0, len(s)):
    for j in range(i, len(s)):
        temp = str()

        if start and stop:
            temp = start + s[i : j] + stop

        if not start and stop:
            temp = s[i : j] + stop

        if start and not stop:
            temp = start + s[i : j]

        if not start and not stop:
            temp = s[i : j]
        
        if temp in s:
            if temp not in A:
                A.append(temp)
# print(A)

if not A:
    print("-1 0")

R = []
if A:
    for i in range(0, len(A)):
        # print(A[i])
        if len(A[i]) >= 2:
            first = A[i][0]
            second = A[i][1]
        
            j = 0
            while True:
                if s[j] == first:
                    if s[j + 1]== second:
                        R.append([j, len(A[i])])
                        break
                j += 1

        if len(A[i]) == 1:
            first = A[i][0]

            j = 0
            while True:
                if s[j] == first:
                    R.append([j, 1])
                    break
                j += 1
  
R.sort()
# print(R)

if R:
    for i in R:
        t = str(i[0]) + " " + str(i[1])
        print(t)



通过率12/18,未通过用例如下,“对比”看不到,不知道哪里问题
*6
,X72EXH]MdDkqQoHR`'{}[zGJBudZZ,bV$.^7%<\vRpUug2pFS:uSsA9IR'M@s3n0#Y)yUXy:bta@2mASnwm(!\G5?lKMY!FE}|}ug\m`H85Ay;O)o@69+=/pGl,)KHykwX;V6<FynJmh1>7/@!,J[Ve\skQh-#c#xY2dYtHKEOR-cLBR+Z`7wRRbD$JgC_RY2mpL7`D^l%?bG#h\z(vryV:sFBA;`FwHi;;T?I5K_zV-O]Wbx'&WzX<+7y(HYk;Nd":h/!e_Q73HlK#0kLQ:ib;c?QUaDIT4qt';^SCT41)~p@i`=v4m\0[,IABz-lRgd9JP"^%N8r%-@}H'=A9mObtVHOvqf|H<)TmFfb9(b[3XQU>|\_TmmD[W(JK'yY3Blj:oVmR'?@CDiZt6`B|cg!&?v-;gT<wvKq;SJ@-AK!hK4FM=v=0g}{US9-AyVdHvU#;~~V(:`RNAV@MMhU$,gj~H3?X'w=U\a#noR1OKy#DdTG2d\jviZa7arTjJC<!a}$U;@Up'Kh_/}UJYgQN&}'`l{GJuWt|Ou>;.Cl%NN&/;h|.3(Wb/DnzMX8#yTEHy8k>KU_<DD/bQ/}WP#vN1%f{#73&GzchbXhB4lGt"zmi%hmW`!N"%wPL^&k4$?F+~B,/#s!S3Iswy2^%>S<k7IG,iyIrm$91uKyB(_'mgK,N2Qrp[&FrwIm)BrUn4T;bBOeT{0[1d~4#0~f^'CVA~7kqCN/9z;tuRHqsHqhfGa^Hxps/U},SxF1/T)bs;a7{E!jJx9f~9!l%Mu!sw>$.4dEdYd^fI_qtGA~J/v>+.P~a{Uxkep6fip,vJotw?BDX'\"?u#mPh^8>h

发表于 2026-01-04 21:25:17 回复(0)

热门推荐

通过挑战的用户

查看代码
实现字通配符*