P4112 [HEOI2015] Shortest Uncommon Substring

Tired of problems about the longest common substrings and subsequences, you decide to go the other way. Definitions: - A "substring" of a string is a contiguous segment of it. For example, `bcd` is a substring of `abcdef`, but `bde` is not. - A "subsequence" of a string is a segment that does not need to be contiguous. For example, `bde` is a subsequence of `abcdef`, but `bdd` is not. Given two lowercase strings $a, b$, please compute: 1. A shortest substring of $a$ that is not a substring of $b$. 2. A shortest substring of $a$ that is not a subsequence of $b$. 3. A shortest subsequence of $a$ that is not a substring of $b$. 4. A shortest subsequence of $a$ that is not a subsequence of $b$.

There are two lines, each containing a string of lowercase letters, representing $a$ and $b$ respectively.

Output $4$ lines, each containing one integer, representing the lengths of the answers to the above $4$ questions in order. If there is no valid answer, output $-1$.

Constraints: - For $20\%$ of the testdata, the lengths of $a$ and $b$ do not exceed $20$. - For $50\%$ of the testdata, the lengths of $a$ and $b$ do not exceed $500$. - For $100\%$ of the testdata, the lengths of $a$ and $b$ do not exceed $2000$. Translated by ChatGPT 5