寻找子串

[编程题]寻找子串

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

给出 m 个字符串 S1，S2，...，Sm 和一个单独的字符串 T 。请在 T 中选出尽可能多的子串同时满足：

1）这些子串在 T 中互不相交。

2）这些子串都是 S1，S2，...，Sm 中的某个串。

问最多能选出多少个子串。

数据范围： $1 \le m \le 10 \$ ，输入的每个字符串长度满足 $1 \le n \le 10^5 \$

输入描述:

第一行一个数m（1≤m≤10），接下来m行，每行一个串。最后一行输入一个串T。输入中所有单个串的长度不超过100000，串中只会出现小写字母。

输出描述:

输出一个数，最多能选出多少串。

示例1

输入

3
aa
b
ac
bbaac

输出

说明

可选 b b aa 或 b b ac

算法知识视频讲解

Python

白色纯度

给出一个python2能AC 90%的代码，时间超时了。我觉得不是思路的锅，大家也可以帮我看一下错误哈！

思路：

1. 将题目给出的子串与原字符串T比对，并给出匹配子串在原字符串中的起始和末尾区间端点。然后将这些区间保存在 intervals中，求这些区间的最大不相交区间个数即可！

2. 最大不相交区间个数怎么求？将这些区间的右端点从小到大排序，然后依次比对当前区间的右端点和下个区间的左端点即可。

这里一定要注意，子串在原字符串出现的位置可能有多个，因此务必把每个区间都要统计上。

def is_sub(p,s):
    i = 0
    while i <= len(s)-len(p):
        if s[i]==p[0]:
            if s[i:i+len(p)]==p:
                intervals.append([i,i+len(p)])
        i += 1
def method(array):
    if not array:
        return 0
    array.sort(key=lambda x:x[1])
    ans = 1
    i = 0
    rec = array[0][1]
    while i < len(array)-1:
        if rec<=array[i+1][0]:
            rec = array[i+1][1]
            ans += 1
        i += 1
    return ans
if __name__=='__main__':
    m = int(raw_input().strip())
    res = []
    for _ in range(m):
        res.append(raw_input().strip())
    t = raw_input().strip()
    intervals = []
    for word in res:
        is_sub(word,t)
    print(method(intervals))

发表于 2019-08-19 19:44:37 回复(0)