Python字符串子序列II

摘要：def find_last_subsequence(target, source):m = len(target)n = len(source)if m == 0:return 0if n == 0 or m > n:return -1# 逆向匹配i = m

def find_last_subsequence(target, source):m = len(target)n = len(source)if m == 0:return 0if n == 0 or m > n:return -1# 逆向匹配i = m - 1 # target的指针j = n - 1 # source的指针while j >= 0 and i >= 0:if source[j] == target[i]:i -= 1j -= 1if i == -1:return j + 1 # 起始位置是j+1，因为j在匹配时已经减1else:return -1# 读取输入target = input.stripsource = input.strip# 获取最后一个子序列的起始位置result = find_last_subsequence(target, source)print(result)输入处理：读取输入的 target 和 source 字符串。初始化指针：i 初始化为 target 的最后一个字符的索引，j 初始化为 source 的最后一个字符的索引。逆向匹配：从后向前遍历 source，当 source[j] 与 target[i] 匹配时，移动 target 的指针 i 向前。确定起始位置：如果 i 移动到 -1，表示找到了完整的子序列，起始位置为 j + 1（因为 j 在匹配时已经减1）；否则返回 -1。

该方法确保正确找到最后一个子序列的起始位置，且时间复杂度为 O(n)，适用于大规模数据。