M30637: 合法出栈序列pub

stack, math, http://cs101.openjudge.cn/practice/M30637/

给定一个由大小写字母和数字构成的，没有重复字符的长度不超过62的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。

要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。

再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。

输入

第一行是原始字符串x 后面有若干行(不超过50行)，每行一个字符串，所有字符串长度不超过100

输出

对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO"

样例输入

abc
abc
bca
cab

样例输出

YES
YES
NO

来源

http://cs101.openjudge.cn/practice/22068/

栈模拟。O(N)

python

import sys

def solve():
    # 读取所有输入行并去除两端的空白字符
    input_data = sys.stdin.read().splitlines()
    if not input_data:
        return

    # 第一行是原始入栈顺序字符串 x
    x = input_data[0].strip()
    
    # 后续行是需要判断的序列
    for line in input_data[1:]:
        target = line.strip()
        
        # 1. 长度如果不相等，肯定不是合法出栈序列
        if len(target) != len(x):
            print("NO")
            continue
            
        # 2. 模拟入栈出栈过程
        stack = []
        x_idx = 0  # 指向 x 中准备入栈的字符
        target_idx = 0  # 指向 target 中准备匹配的字符
        
        is_possible = True
        
        # 将 x 中的字符依次入栈
        for char in x:
            stack.append(char)
            # 只要栈不为空，且栈顶元素等于当前目标序列需要出栈的元素
            while stack and target_idx < len(target) and stack[-1] == target[target_idx]:
                stack.pop()
                target_idx += 1
        
        # 如果最后栈清空了，且目标序列所有字符都匹配完了
        if not stack and target_idx == len(x):
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    solve()

思路：栈的判定定理，即栈排列（Stack Permutation）的数学性质：

3-1-2 模式规避：在数学中，一个序列是合法的栈排列，当且仅当它不包含“3-1-2”模式。本质上是在检测是否存在这个数学上的“非法模式”。
将物理过程抽象成了索引的空间关系。这种从具体过程到抽象规律的转化，是典型的数学思维。

逻辑：

预处理：记录原字符串 xx 中每个字符的位置索引。
合法性检查：先检查集合是否相等、长度是否一致。
核心算法：维护一个当前已出现的“最靠后”的字符位置 max_index_seen。如果当前字符的原始位置 current_idx 小于 max_index_seen，说明它是在之前某个字符入栈时被压入的。按照栈的性质，在 current_idx 到 max_index_seen 之间的所有字符必须在 current_idx 之前就已经出栈了。
复杂度：外层循环 NN（字符串长度），内层循环检查 nj 到 mm 之间的空隙，最坏复杂度 O(N^2)。

python

import sys

def is_valid_stack_sequence(target_str, char_to_index, original_set, n):
    """
    判断 target_str 是否是合法的出栈序列。
    逻辑：检查是否存在“3-1-2”模式，即如果一个较晚入栈的字符先出栈，
    则夹在它们中间的字符必须已经全部出栈。
    """
    # 快速剪枝：长度不等或字符集不一致
    if len(target_str) != n or set(target_str) != original_set:
        return False

    is_popped = [False] * n
    max_index_seen = -1

    for char in target_str:
        current_idx = char_to_index[char]
        
        if current_idx > max_index_seen:
            # 当前字符是目前位置最靠后的（新高水位）
            max_index_seen = current_idx
        else:
            # 当前字符位置在之前出现的最大位置之前
            # 检查 current_idx 到 max_index_seen 之间的所有字符是否已出栈
            for middle_idx in range(current_idx + 1, max_index_seen):
                if not is_popped[middle_idx]:
                    return False
        
        # 标记当前字符已出栈
        is_popped[current_idx] = True
        
    return True

def solve():
    # 使用读取生成器，处理可能的空行
    input_iter = (line.strip() for line in sys.stdin if line.strip())
    
    try:
        original_word = next(input_iter)
    except StopIteration:
        return

    # 预处理原始字符串信息
    n = len(original_word)
    original_set = set(original_word)
    char_to_index = {char: i for i, char in enumerate(original_word)}

    # 处理后续每一个待测字符串
    results = []
    for test_str in input_iter:
        if is_valid_stack_sequence(test_str, char_to_index, original_set, n):
            results.append("YES")
        else:
            results.append("NO")

    # 批量输出结果
    if results:
        sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

M30637: 合法出栈序列pub ​

M30637: 合法出栈序列pub