我要招人

去企业版

首页 > 试题广场 >

判断是不是子字符串

[编程题]判断是不是子字符串

热度指数：8165 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串 s和 t ，判断 s是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度n ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

输入描述:

共两行，第一行为字符串s,  第二行为字符串t
字符串t的长度 1<=n<=500000
字符串s的长度 1<=m<=100

输出描述:

输出true或者是false，true表示是s是t的子序列，false表示s不是t的子序列

示例1

输入

abc
ahbgdc

输出

true

示例2

输入

axc
ahbgdc

输出

false

算法知识视频讲解

Python

牛客105721676号

import sys

lst = []

result = 'true'

for line in sys.stdin:

a = line.split()

lst.append(a[0])

if len(lst) ==2:

for x in lst[0]:

if x in lst[1]:

lst[1] = lst[1][lst[1].index(x):]

else:

result = 'false'

break

print( result)

lst = []

编辑于 2026-03-31 13:35:20 回复(0)

Python

牛客226836090号

s=input() #短
t=input() #长
cnt=0
for i in t:
    if cnt>=len(s):
        break
    elif s[cnt]==i:
        cnt+=1
        continue
    else:
        continue
if cnt==len(s):
    print('true')
else:
    print('false')
"""
遍历长的
判断短的中是否在长的中，
如果在长的中，短的长的就都向后移一个，
如果不在长的中，短的不动，长的向后移一个
注意如果短的遍历完长的还没有遍历完要提前结束
"""

发表于 2025-09-25 21:00:49 回复(0)

Python

准备笔试的我很踏实

S = [c for c in input()]
L = [c for c in input()]
flag = False
for c in L:
    if c == S[0]:
        S.pop(0)
    if not len(S):
        flag = True
        break
if flag:
    print("true")
else:
    print("false")

发表于 2025-07-04 11:15:45 回复(0)

Python

星语Wishes

s = input() #查询的字符串

t = input() #长字符串

s1 = ""

r = 0 # 位符

for i in range(len(s)):

s1 = s[i]

num = t.find(s1,r)

r = num

if num == -1:

print("false")

break

elif i == len(s)-1:

print("true")

发表于 2025-03-05 12:00:28 回复(0)

Python

牛客1g

import re    

s1="abc"
s2="ahbgdc"
print(re.search("\w+".join(list(s1)),s2) is not None)

发表于 2024-09-10 21:59:45 回复(0)

Python

小牛冲冲冲吖

我觉得时间复杂度是O(n)

import sys

a_line = next(sys.stdin)
b_line = next(sys.stdin)
start = 0
end = len(a_line) - 1
for i in b_line:
    if i == a_line[start]:
        start += 1
    if start == end:
        break
if start == end:
    print("true")
else:
    print("false")

编辑于 2024-03-07 13:19:01 回复(0)

Python

牛客129142181号

t = input("请输入子字符串:")
s = input("请输入字符串:")

start = 0
flag = 0
for i in t:
    if s.find(i, start) != -1:
        start = s.find(i)
    else:
        print('false')
        flag = 1
        break
if not flag:
    print('true')

编辑于 2023-12-03 19:56:45 回复(0)

Python

我想成为大神

s, t = input(), input()
begin = 0  # 定义在字符串t中开始查找s字符的起始位置
result = True
# 在字符串t中逐个查找s的每个字符
for i in range(len(s)):
    if s[i] in t[begin:]:  # 当找到s[i]时，修改下次查找s[i+1]时t的起始位置
        begin = begin + t[begin:].find(s[i])
    else:  # 如果s[i]没有找到则结束循环
        result = False
        break

if not result:
    print('false')
else:
    print('true')

发表于 2023-11-14 12:05:01 回复(0)

Python

豁达的代码渣渣在看机会

import sys

def huawei_4(s: str, t: str):

"""判断是不是子序列"""

j = 0

for i in t:

if i == s[j]:

j += 1

if j == len(s):

return "true"

return "false"

if __name__ == "__main__":

s = input()

t = input()

print(huawei_4(s, t))

发表于 2023-03-25 22:31:09 回复(0)

Python

无语的悲伤蛙在刷代码

while True:
    try:
        s = input()
        t = input()
        #记录结果
        tmp = ''
        #历遍s，按顺序比对t中是否出现
        for i in range(len(s)):
            #历遍t
            for v, k in enumerate(t):
                #如果t中查询到s中的字母，将该字母加入tmp,并更新t
                if s[i] == k:
                    tmp += k
                    #更新t,避免重复查询
                    t = t[v + 1::]
                    break
                    
        #比较结果，如果tmp和s相同就是true，反之false
        if tmp == s:
            print('true')
        else:
            print('false')
    except:
        break

发表于 2023-03-11 18:39:29 回复(0)

Python

牛客509987575号

target = input()
source = input()

index = -1
for ch in target[::-1]:
    index = source.rfind(ch)
    if index != -1:
        source = source[0:index]
    else:
        break
print('false' if index == -1 else 'true')

发表于 2022-06-18 19:34:38 回复(0)