给出 m 个字符串 S1,S2,...,Sm 和一个单独的字符串 T 。请在 T 中选出尽可能多的子串同时满足:
1)这些子串在 T 中互不相交。
2)这些子串都是 S1,S2,...,Sm 中的某个串。
问最多能选出多少个子串。
数据范围: ,输入的每个字符串长度满足
第一行一个数m(1≤m≤10),接下来m行,每行一个串。最后一行输入一个串T。输入中所有单个串的长度不超过100000,串中只会出现小写字母。
输出一个数,最多能选出多少串。
3 aa b ac bbaac
3
可选 b b aa 或 b b ac
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))