给出一个只包含0和1的字符串(长度在1到100之间),求其每一个子串出现的次数 输入格式 一行,一个01字符串。 输出格式 对所有出现次数在1次以上的子串,输出该子串及出现次数,中间用单个空格隔开。按子串的字典序从小到大依次输出,每行一个。 样例
时间: 2024-09-06 20:08:13 浏览: 32
这个问题可以使用滑动窗口和哈希映射的方式来解决。以下是步骤:
1. 首先,创建一个哈希表(Python 中可以用 dict 或者 collections.Counter,Java 中可以用 HashMap)来存储每个子串及其出现的次数。
2. 定义两个指针,left 和 right,初始时 left 指向开始位置,right 指向下一个字符的位置。
3. 当 right 边界到达字符串末尾时,将子串 s[left:right] 的计数添加到哈希表中,并更新 left 到 right-1 之间的子串计数(如果新的子串与旧子串相同,则计数加一)。
4. 将 left 指针右移一位,继续处理新子串。
5. 遍历哈希表,找到出现次数大于1的子串并按照字典序输出它们及其出现次数。
这是一个 Python 示例代码实现:
```python
def count_substrings(s):
counter = {}
left, right = 0, 0
while right < len(s):
sub_str = s[left:right+1]
if sub_str in counter:
counter[sub_str] += 1
else:
counter[sub_str] = 1
while (left < right and
(counter[s[left:right+1]] == 1 or
(s[left] != '0' and s[left+1] == '1') or
(s[left] == '1' and s[left+1] != '0'))):
counter[s[left:right+1]] -= 1
left += 1
right += 1
result = [f"{k} {v}" for k, v in sorted(counter.items()) if v > 1]
return "\n".join(result)
# 测试样例
input_str = "0110011"
print(count_substrings(input_str))
```
阅读全文