首页 > 试题广场 >

序列模式匹配

[编程题]序列模式匹配

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

给定文本text和待匹配字符串pattern，二者皆只包含小写字母，并且不为空。
在text中找出匹配pattern的最短字符串，匹配指按序包含pattern，但不要求pattern连续。
如text为abaacxbcbbbbacc，pattern为cbc，text中满足条件的是abaacxbcbbbbacc下划线部分。

输入描述:

多行，每行一个text和一个pattern，用空格分隔。
保证1<=|text|,|pattern|<=1000，Σ|text|,Σ|pattern|<=10000。

输出描述:

输出最短匹配序列起止位置（位置下标从0开始），用空格分隔。若有多个答案，输出起止位置最小的答案；若无满足条件的答案，则起止均为-1。

示例1

输入

abaacxbcbbbbacc cbc
abc x
aaabcac ac

输出

4 7
-1 -1
5 6

算法知识视频讲解

Python

贾志统

import sys

def func(a, b):
    temp = {}
    i = 0
    j = 0
    start = -1
    end = -1
    
    while i < len(a):
        if a[i] == b[j]:
            j += 1
            
            if start == -1:
                start = i
                end = i
            else:
                end = i
            
            if j == len(b):
                if end - start not in temp:
                    temp[end-start] = [start, end]
                i = start
                j = 0
                start = -1
        i += 1
    if len(temp) > 0:
        res = temp[min(temp.keys())]
    else:
        res = [-1, -1]
    res_str = str(res[0]) + " " + str(res[1])
    print(res_str)


lines = sys.stdin.readlines()
for line in lines:
    text, pattern = line.strip().split()
    func(text, pattern)

发表于 2019-09-08 10:49:30 回复(1)