python编程题解答: <成步堂龙一> 是一名律师。在法庭开庭时,他需要出示手中的证物来击破他的老对手,检察官 <御剑怜侍> 询问的各个疑点, 以此证明委托人(被告)的清白。 检察官有一张询问清单 s,s中是是n个长度不超过20的字符串,代表所有的质询。 成步堂手上有一张证物清单s2, s2是一个长度不超过20的字符串。 已知,若质询是证物清单的子单,那么该质询会被击破。证物清单可以使用多次。同时,成步堂可以将思路逆转过来,若将质询逆转后是证物清单的子单,该质询也会被击破。 请问,成步堂能否击破检察官提出的所有质询? 输入格式: 第一行是一个正整数n,代表质询的总数。 第2-n+1行是n个字符串,代表每个质询。 第n+2行是一个字符串s2,代表物证清单。 输出格式: 输出共一行,若能完成大逆转(将所有质询击破),输出“Objection!”;否则,输出检查官剩余的质询数量。 输入样例1: 2 cba abc bbbbbabcaaaa 输出样例1: Objection! 输入样例2: 3 aaabbbcccabc aaabbbccc bacabc aaabacabc 输出样例2: 2
时间: 2024-03-20 19:44:28 浏览: 66
这是一道字符串匹配问题。我们可以遍历所有质询,检查它们是否是证物清单的子单或者逆转后是证物清单的子单。如果所有质询都能被击破,那么成步堂就能完成大逆转。否则,输出剩余的质询数量。
代码如下:
```python
def is_subseq(s, t):
"""判断s是否是t的子序列"""
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
def reverse(s):
"""返回s的逆序字符串"""
return s[::-1]
n = int(input())
queries = [input().strip() for i in range(n)]
evidence = input().strip()
count = 0
for query in queries:
if is_subseq(query, evidence) or is_subseq(reverse(query), evidence):
count += 1
if count == n:
print("Objection!")
else:
print(n-count)
```
时间复杂度为$O(n\times L)$,其中$n$是质询的总数,$L$是质询的平均长度。
阅读全文