计算子字符串:在给定的文本中，找出以A开头、以B结尾的子字符串的数量
计算子字符串:在给定的文本中，找出以A开头、以B结尾的子字符串的数量
提问于 2018-02-11 06:06:33
例如，CABAAXBYA中有四个这样的子字符串。
我最初使用的蛮力算法是，使用外部的for循环，每当我遇到一个A时，我就进入另一个for循环来检查是否存在B。如果找到B，我会递增计数。最后，存储在count变量中的值产生所需的结果。
我在阅读字符串匹配算法时遇到了一个问题，当你从右向左而不是从左向右遍历时，你的算法效率更高，但这里的子字符串并不是作为函数的参数给出的，而你将使用它来计算所需的值。
我的问题是，如果我从右到左而不是从左到右遍历字符串，是否会使我的算法在任何情况下都更有效？
回答 1
Stack Overflow用户
发布于 2018-02-11 06:34:05
以下是向后迭代字符串可能导致O(n)计算而不是原来的O(n^2)工作的一种方法：
A = "CABAAXBYA"
count = 0 # Number of B's seen
total = 0
for a in reversed(A):
if a=='B':
count += 1
elif a=='A':
total += count
print total这是通过跟踪当前点右侧的B的数量来实现的。
(当然，您也可以通过向左计数A的数量来使用forwards迭代获得相同的结果：
count = 0 # Number of A's seen
total = 0
for a in A:
if a=='A':
count += 1
elif a=='B':
total += count
print total)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48726056
复制相关文章
相似问题
腾讯云开发者
