2045C.md (1973B)
1 Source: https://codeforces.com/problemset/problem/2045/C 2 3 C. Saraga 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 1024 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The word saraga is an abbreviation of sarana olahraga, an Indonesian term for a sports facility. It is created by taking the prefix sara of the word sarana and the suffix ga of the word olahraga. Interestingly, it can also be created by the prefix sa of the word sarana and the suffix raga of the word olahraga. 22 23 An abbreviation of two strings $S$ and $T$ is interesting if there are at least two different ways to split the abbreviation into two non-empty substrings such that the first substring is a prefix of $S$ and the second substring is a suffix of $T$. 24 25 You are given two strings $S$ and $T$. You want to create an interesting abbreviation of strings $S$ and $T$ with minimum length, or determine if it is impossible to create an interesting abbreviation. 26 27 Input 28 29 The first line consists of a string $S$ ($1 \leq |S| \leq 200\,000$). 30 31 The second line consists of a string $T$ ($1 \leq |T| \leq 200\,000$). 32 33 Both strings $S$ and $T$ only consist of lowercase English letters. 34 35 Output 36 37 If it is impossible to create an interesting abbreviation, output -1. 38 39 Otherwise, output a string in a single line representing an interesting abbreviation of strings $S$ and $T$ with minimum length. If there are multiple solutions, output any of them. 40 41 Examples 42 43 Input 44 45 ``` 46 sarana 47 olahraga 48 ``` 49 50 Output 51 52 ``` 53 saga 54 ``` 55 56 Input 57 58 ``` 59 berhiber 60 wortelhijau 61 ``` 62 63 Output 64 65 ``` 66 berhijau 67 ``` 68 69 Input 70 71 ``` 72 icpc 73 icpc 74 ``` 75 76 Output 77 78 ``` 79 icpc 80 ``` 81 82 Input 83 84 ``` 85 icpc 86 jakarta 87 ``` 88 89 Output 90 91 ``` 92 -1 93 ``` 94 95 Note 96 97 Explanation for the sample input/output #1 98 99 You can split saga into s and aga, or sa and ga. The abbreviation saraga is interesting, but saga has a smaller length. 100 101 Explanation for the sample input/output #2 102 103 The abbreviation belhijau is also interesting with minimum length, so it is another valid solution.