codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.