华为OD-2024年E卷-增强的strstr[100分] -- python

问题描述：

C语言有一个库函数:char*strstr(const char *haystack, const char *needle)，实现在字符haystack 中查找第一次出现字符串needle的位置，如果未找到则返回null。现要求实现一个strstr的增强函数，可以使用带可选段的字符串来模糊查询，与strstr一样返回首次查找到的字符串位置。可选段使用“[]”标识，表示该位置是可选段中任意一个字符即可满足匹配条件。比如“a[bc]”表示可以匹配“ab"或“ac”。注意目标字符串中可选段可能出现多次。
输入描述
与strstr函数一样，输入参数是两个字符串指针，分别是源字符串和目标字符串。
输出描述
与strstr函数不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移(从0开始算)，如果没有匹配返回-1。
补充说明
源字符串中必定不包含[';目标字符串中叮必定成对出现，且不会出现嵌套。输入的字符串长度在[1,100]之间。

abcd
b[cd]

1

解题思路：

将目标字符串按 [] 拆分为所有可能的字符串，遍历源字符串，输出最先匹配的索引，否则输出-1

拆分：

1. 使用列表 l 记录所有可能的目标字符串，初始化为空： ''
2. 在 [ 之前：给列表 l 中所有元素分别加上当前字符
3. 在 ] 之前（即 [] 内）：对列表 l 中所有元素与 [] 内字符作笛卡尔积

结束条件：

1. 当前字符索引 < 目标字符长度
2. 目标字符串总是以 [ 之前作为结束

代码实现：

s = input()
t = input()
l = []
l.append('')
i = 0
while i < len(t):
    # [之前，给每个字符串都加上当前字符
    while i < len(t) and t[i] != '[':
        for j in range(len(l)):
            l[j] += t[i]
        i += 1
    i += 1# [ 的下一个
    if i >= len(t):# [ 之前，可能作为结束条件
        break
    # ] 之前，给每个字符串分别与[]内每个字符作笛卡尔积
    tem = []
    while i < len(t) and t[i] != ']':
        for j in l:
            j += t[i]
            tem.append(j)
        i += 1
    l = tem 
    i += 1# ] 的下一个
print(l)
f = True
for test in l:
    for i in range(len(s)):
        if s[i:i+(len(test))] == test:
            f = False
            print(i)
            break
if f:
    print(-1)