Open Wizmann opened 3 years ago
Problem
一个多线程程序，每个线程都会向一个输出源（例如stdout）打印字符串"TMT"。每个线程会输出一个或多个完整的TMT字符串（即不存在输出一半的情况）。
多线程输出可能会导致输出之间的交错。如：T1 T2 M1 M2 T2 T1。(T1表示线程1输出的T字符）
给定一个字符串，问是否可能是这个程序输出的结果。
如果问题简化为ABC字符串，那么我们可以贪心A后面最近的B，B后面最近的C。因为对于合法字符串，一定有A1 < (A2, B1) < (C1, B2) < C2。所以易得B1 < B2，C1 < C2。
对于TMT字符串，我们无法区别第一个T和第二个T。例如"Ta Ma Tb Mb Tc Td"，如果我们匹配"Ta Ma Tb"，那么剩余的部分无法继续匹配，这明显是有问题的。
我们将每个TMT字符串的第二个T记为小t。对于任意TMT字符串，如果小t在大T的左面，我们可以安全的交换大T小t。原理很简单，因为大T在对应M的左面，将其往左置换并不会有什么后果。小t在M的右面，向右置换也是安全的。
所以在经过若干次的置换之后，所有的大T一定在所有的小t左面。我们已经将TMT字符串转化为了TMt字符串，再使用ABC串的结论，使用贪心匹配算法即可。
Code
题意
Problem
一个多线程程序，每个线程都会向一个输出源（例如stdout）打印字符串"TMT"。每个线程会输出一个或多个完整的TMT字符串（即不存在输出一半的情况）。
多线程输出可能会导致输出之间的交错。如：T1 T2 M1 M2 T2 T1。(T1表示线程1输出的T字符）
给定一个字符串，问是否可能是这个程序输出的结果。
解法
如果问题简化为ABC字符串，那么我们可以贪心A后面最近的B，B后面最近的C。因为对于合法字符串，一定有A1 < (A2, B1) < (C1, B2) < C2。所以易得B1 < B2，C1 < C2。
对于TMT字符串，我们无法区别第一个T和第二个T。例如"Ta Ma Tb Mb Tc Td"，如果我们匹配"Ta Ma Tb"，那么剩余的部分无法继续匹配，这明显是有问题的。
我们将每个TMT字符串的第二个T记为小t。对于任意TMT字符串，如果小t在大T的左面，我们可以安全的交换大T小t。原理很简单，因为大T在对应M的左面，将其往左置换并不会有什么后果。小t在M的右面，向右置换也是安全的。
所以在经过若干次的置换之后，所有的大T一定在所有的小t左面。我们已经将TMT字符串转化为了TMt字符串，再使用ABC串的结论，使用贪心匹配算法即可。
Code