主页 / 问题 / 1596590
Accepted
A1pha
Asked:2024-10-13 20:59:10 +0800 CST2024-10-13 20:59:10 +0800 CST

使用 re 查找文本文件中最长的子字符串

  • 772

问题条件是：

文本文件包含一串字符，其中可能包括拉丁字母 A...Z 的大写字母。求恰好包含三个 Z（不一定是相邻的）的最长子串的长度。

我想到了使用 re 库来解决这个问题：

import re

with open("text.txt") as file:
    string = file.read()

    substrings = re.findall(r"[^Z]*Z" * 3 + r"[^Z]*", string)

    print(len(max(substrings, key=len)))

但答案不匹配：正确的是338，代码显示297。你能告诉我错误是什么吗？

python

4 个回答

  1. Best Answer

    正则表达式引擎不会返回重叠的匹配项。也就是说，并不是所有搜索到的子串都会被扫描，而是每四个子串都会被扫描一次。没有简单的方法可以解决这种情况。

    1

    解决方案没有re.我们读取文件，将其拆分为不带“Z”的单词，返回这些单词的长度。我们根据长度建立累积和sums。使用累积和列表，让我们使用两个间隔为四个位置的迭代器。迭代器之间的差异是四个连续单词的长度之和。我们选择最大值，添加三个以纪念四个单词之间删除的三个分隔符：

    def cumsum(seq):
    s = 0
    yield s
    for v in seq:
        s += v
        yield s


with open('24_3.txt') as f:
    sums = tuple(cumsum(map(len, f.read().split('Z'))))

it1 = iter(sums)
for _ in range(4):
    next(it1)
print(max(b - a for a, b in zip(sums, it1)) + 3)

    如果你不介意再次复制数据，最后四行可以替换为一行：

    print(max(b - a for a, b in zip(sums, sums[4:])) + 3)

    2

    可以制定无需线性附加内存的解决方案。chars(f)打印文件中的连续字符。zs(seq)返回序列中“Z”字符的位置seq。此外，它还给出了序列的开始 ( -1itertools.tee ) 和结束位置，就好像它被“Z”字符包围一样。接受一个迭代器并制作它的两个副本。在底层，它会记住原始迭代器的值。在我们的问题中，他会记住四个整数——常量记忆。

    两个迭代器沿着位置序列运行，间隔为四个位置。迭代器之间的差异是不带“Z”的四个连续单词的总长度。我们选择最大值，减去一：行尾有一个额外的字符“Z”。

    这是一个恒定内存的解决方案，您可以处理任何大小的文件：

    import itertools


def chars(f):
    while c := f.read(1):
        yield c


def zs(seq):
    yield -1
    i = -1 # to process empty seq
    for i, c in enumerate(seq):
        if c == 'Z':
            yield i
    yield i + 1
            

with open('24_3.txt') as f:
    it1, it2 = itertools.tee(zs(chars(f)))

    for _ in range(4):
        next(it2)
    print(max(b - a for a, b in zip(it1, it2)) - 1)

    PS在第一个程序中，该块for被删除，with因为正在内存中创建文件的副本。在第二个程序中，该块必须保留在内部。

    itertools.tee出于教育目的，可以将PPSinterval(seq, k)替换为一个函数，该函数接受seq并返回彼此相距一定距离的值对k。那么计算逻辑就变成了一行：文件中的字符→'Z'位置→位置间隔→最大间隔长度：

    def interval(seq, k):
    it = iter(seq)
    ring = [v for v, _ in zip(it, range(k))]
    i = 0
    for v in it:
        yield ring[i], v
        ring[i] = v
        i = (i + 1) % k


with open('/home/sv/Downloads/24_3.txt') as f:
    print(max(b - a for a, b in interval(zs(chars(f)), 4)) - 1)
    • 6

  2. 准备好用于测试的控制台脚本（该行AZBZCZDZEEE输出9）：

    def longest_substring_with_three_z(v_file):
    with open(v_file, "r") as h: v_data = h.read()
    
    v_result = v_start = v_count = 0
    
    for v_end, v_char in enumerate(v_data):
        v_count += v_char == "Z"  # Увеличиваем счетчик, если текущий символ "Z"
            
        # Если количество "Z" больше 3, сдвигаем начало подцепочки вправо
        while v_count > 3:
            v_count -= v_data[v_start] == "Z"  # Уменьшаем счетчик, если символ в начале подцепочки "Z"
            v_start += 1  # Сдвигаем начало подцепочки вправо
            
        # Если в подцепочке ровно 3 "Z", обновляем максимальную длину
        if v_count == 3: v_result = max(v_result, v_end - v_start + 1)
    
    return v_result
    
# Пример использования:
import os
    
print("-" * 75 + "\nДлина самой длинной подцепочки в тексте, в которой есть ровно три буквы Z:\n" + "-" * 75)
    
v_file = "input.txt"
if not os.path.exists(v_file): print(f"Файл {v_file} не найден в текущем каталоге!")
else: print(f"Результат: {longest_substring_with_three_z(v_file)}")
    
print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")
    • 3

  3. 由于生成器的轻微复杂性和队列的内存消耗，队列的大小不会超过所需 Z 的数量（本例中为 3 个）加 1，因此我们获得了现成的链长度，我们需要从中选择最大的一个。

    如果在最后一行我们将“(c for c in data)”更改为 Stanislav 的 chars(f) 函数，那么一切都应该正常。

    PS 如果需要，您可以轻松获取链的起始和结束索引。

    from collections import deque

data = "AZBZCZDZEEE"
char_Z = 'Z'
count_Z = 3

def sequence_length(symbol, iterable, scount):
    idx_store = deque()
    idx_store.append(-1)
    for idx, symb in enumerate(iterable):
        if symb == symbol:
            if len(idx_store) - 1 == scount:
                yield idx - idx_store.popleft() - 1
            idx_store.append(idx)
    if len(idx_store) - 1 == scount:
        yield idx - idx_store.popleft()

print(max(sequence_length(char_Z, (c for c in data), count_Z), default=None))
    • 2

  4. 总的来说，我明白发生了什么：findall函数不会一次找到所有子字符串，而是首先查找、记录并且不再考虑，这就是为什么它得到错误答案的原因。

    如果有人能想到这一点，我将不胜感激。在我看来，这个方法并不能解决这个问题。

    • 0

相关问题