102170: [AtCoder]ABC217 A - Lexicographic Order

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings $S$ and $T$.

Below, let $S_i$ denote the $i$-th character of $S$. Also, if $S$ is lexicographically smaller than $T$, we will denote that fact as $S \lt T$; if $S$ is lexicographically larger than $T$, we will denote that fact as $S \gt T$.

1. Let $L$ be the smaller of the lengths of $S$ and $T$. For each $i=1,2,\dots,L$, we check whether $S_i$ and $T_i$ are the same.
2. If there is an $i$ such that $S_i \neq T_i$, let $j$ be the smallest such $i$. Then, we compare $S_j$ and $T_j$. If $S_j$ comes earlier than $T_j$ in alphabetical order, we determine that $S \lt T$ and quit; if $S_j$ comes later than $T_j$, we determine that $S \gt T$ and quit.
3. If there is no $i$ such that $S_i \neq T_i$, we compare the lengths of $S$ and $T$. If $S$ is shorter than $T$, we determine that $S \lt T$ and quit; if $S$ is longer than $T$, we determine that $S \gt T$ and quit.

简单来说，字典序就是字典中单词的排列顺序。更正式的定义是，确定不同字符串$S$和$T$之间字典序的方法如下。

以下，我们用$S_i$表示字符串$S$的第$i$个字符。如果$S$在字典序上小于$T$，我们用$S \lt T$表示；如果$S$在字典序上大于$T$，我们用$S \gt T$表示。

1. 让$L$为字符串$S$和$T$中长度较小的一个。对于每个$i=1,2,\dots,L$，我们检查$S_i$和$T_i$是否相同。
2. 如果存在一个$i$，使得$S_i \neq T_i$，那么让$j$为这样的$i$中的最小值。然后，我们比较$S_j$和$T_j$。如果$S_j$在字母顺序上比$T_j$靠前，我们确定$S \lt T$并退出；如果$S_j$在字母顺序上比$T_j$靠后，我们确定$S \gt T$并退出。
3. 如果不存在一个$i$，使得$S_i \neq T_i$，我们比较字符串$S$和$T$的长度。如果$S$比$T$短，我们确定$S \lt T$并退出；如果$S$比$T$长，我们确定$S \gt T$并退出。