小团的神秘暗号

发布于2021-04-16

上次编辑2021-04-16

问题描述

小团深谙保密工作的重要性，因此在某些明文的传输中会使用一种加密策略，小团如果需要传输一个字符串 S ，则他会为这个字符串添加一个头部字符串和一个尾部字符串。头部字符串满足至少包含一个 “MT” 子序列，且以 T 结尾。尾部字符串需要满足至少包含一个 “MT” 子序列，且以 M 开头。例如 AAAMT 和 MAAAT 都是一个合法的头部字符串，而 MTAAA 就不是合法的头部字符串。很显然这样的头尾字符串并不一定是唯一的，因此我们还有一个约束，就是 S 是满足头尾字符串合法的情况下的最长的字符串。
很显然这样的加密策略是支持解码的，给出一个加密后的字符串，请你找出中间被加密的字符串 S 。

格式：

输入：
- 输入第一行是一个正整数 n ，表示加密后的字符串总长度。
- 输入第二行是一个长度为 n 的仅由大写字母组成的字符串 T 。
输出：
- 输出仅包含一个字符串 S 。

示例：

输入：
     10
     MMATSATMMT
输出：SATM

提示：

• 1 <= n <= 100000

解题思路

Python

import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


n = readint()
s = readstr()
l, r = 0, n - 1
f = False
while l < n:
    if s[l] == "M":
        f = True
    elif s[l] == "T" and f:
        break
    l += 1
f = False
while r > l:
    if s[r] == "T":
        f = True
    elif s[r] == "M" and f:
        break
    r -= 1
print(s[l + 1 : r])

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    bool f = false;
    int l = 0, r = n - 1;
    for (; l < n; ++l) {
        if (s[l] == 'M') {
            f = true;
        } else if (s[l] == 'T' && f) {
            break;
        }
    }
    f = false;
    for (; r > l; --r) {
        if (s[r] == 'T') {
            f = true;
        } else if (s[r] == 'M' && f) {
            break;
        }
    }
    cout << (l + 1 <= r - 1 ? s.substr(l + 1, r - l - 1) : "") << '\n';
    return 0;
}

返回顶部

在手机上阅读