工作中遇到的数字型字符串算法问题求助

问题描述 #

需要将表示有限长度小数的字符串，转换为用(...)标记循环节的形式：当小数部分存在重复出现的循环子串时，将循环节用括号包裹；无循环节则保持原字符串。输入输出示例如下：

之前尝试滑动窗口算法未成功，这里可以用KMP算法的LPS数组来高效识别循环节，这是处理字符串重复子串问题的经典方案。

解决方案思路 #

1. 拆分输入字符串为整数部分和小数部分，无小数部分直接返回原字符串。
2. 遍历小数部分的所有可能起始位置，寻找最长的有效循环节：
   • 对每个起始位置后的子串计算LPS数组（最长前缀后缀匹配数组），通过数组最后一个元素推导循环节长度。
   • 验证循环节是否重复至少两次（完全重复或末尾部分不完整但前面重复多次）。
3. 找到最长循环节后，按格式拼接整数部分、非循环前缀、带括号的循环节。

代码实现（Python） #

def format_repeating_decimal(s):
    if '.' not in s:
        return s
    integer_part, decimal_part = s.split('.', 1)
    n = len(decimal_part)
    if n == 0:
        return s
    
    best_start = n  # 默认无循环节，起始位置设为小数部分长度
    best_cycle_len = 0
    
    # 遍历所有可能的循环节起始点
    for i in range(n):
        sub = decimal_part[i:]
        sub_len = len(sub)
        if sub_len < 2:
            continue
        
        # 计算当前子串的LPS数组
        lps = [0] * sub_len
        prefix_len = 0  # 当前最长前缀后缀的长度
        j = 1
        while j < sub_len:
            if sub[j] == sub[prefix_len]:
                prefix_len += 1
                lps[j] = prefix_len
                j += 1
            else:
                if prefix_len != 0:
                    prefix_len = lps[prefix_len - 1]
                else:
                    lps[j] = 0
                    j += 1
        
        # 推导循环节长度
        cycle_len = sub_len - lps[-1]
        # 验证循环节有效性：至少重复两次
        if cycle_len < sub_len:
            # 情况1：子串完全由循环节重复构成
            if sub_len % cycle_len == 0:
                if cycle_len > best_cycle_len:
                    best_cycle_len = cycle_len
                    best_start = i
            # 情况2：子串前半部分重复循环节，末尾可能不完整，但至少重复两次
            elif (sub_len - cycle_len) >= cycle_len:
                if sub[:cycle_len] == sub[cycle_len:2*cycle_len]:
                    if cycle_len > best_cycle_len:
                        best_cycle_len = cycle_len
                        best_start = i
    
    # 拼接结果
    if best_cycle_len > 0:
        non_cyclic_prefix = decimal_part[:best_start]
        cycle = decimal_part[best_start:best_start+best_cycle_len]
        return f"{integer_part}.{non_cyclic_prefix}({cycle})"
    else:
        return s

# 测试用例
print(format_repeating_decimal("7.999999999999999999999999"))
print(format_repeating_decimal("0.91877104377104377104377104377104"))
print(format_repeating_decimal("7.428571428571428571428571428571428571"))
print(format_repeating_decimal("0.123"))

关键说明 #

• LPS数组的核心作用是找到子串中最长的相等前缀和后缀，通过这个值可以快速推导循环节长度：循环节长度 = 子串长度 - LPS最后一个值。
• 遍历所有起始位置是为了覆盖“小数部分前半段非循环、后半段循环”的场景（比如第二个测试用例）。
• 双重验证循环节的有效性，避免把偶然重复的短子串误判为循环节。

内容的提问来源于stack exchange，提问作者TangS Wu