
Team Trees
|
All submissions for this problem are available.
### Read problem statements in [Bengali](http://www.codechef.com/download/translated/LTIME78/bengali/PLANT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME78/mandarin/PLANT.pdf), [Russian](http://www.codechef.com/download/translated/LTIME78/russian/PLANT.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME78/vietnamese/PLANT.pdf) as well. You are given a string $S$ with length $N$. You should find two non-intersecting substrings of $S$ such that the second one is a substring of the first one and the product of these substrings' lengths is the maximum possible. More formally, let's denote a contiguous substring $S_l, S_{l+1}, \ldots, S_r$ by $S[l, r]$; you should find integers $l_1$, $r_1$, $l_2$ and $r_2$ which satisfy these four criteria: - $1 \le l_1 \le r_1 \le N$ and $1 \le l_2 \le r_2 \le N$ - $r_2 \lt l_1$ or $r_1 \lt l_2$ - $S[l_2, r_2]$ is a contiguous substring of $S[l_1, r_1]$ - the product $P = (r_2-l_2+1) \cdot (r_1-l_1+1)$ is maximum possible Find the maximum value of $P$. It is guaranteed that for the given test data, there is at least one way to choose $l_1, r_1, l_2, r_2$ such that the first three criteria are satisfied, i.e. the answer is well-defined. ### Input - The first line of the input contains a single integer $N$. - The second line contains a single string $S$ with length $N$. ### Output Print a single line containing one integer ― the maximum product $P$. ### Constraints - $1 \le N \le 2 \cdot 10^6$ - $S$ contains only lowercase English letters ### Subtasks **Subtask #1 (50 points):** $N \le 10^3$ **Subtask #2 (50 points):** original constraints ### Example Input 1 ``` 5 abaab ``` ### Example Output 1 ``` 6 ``` ### Explanation We can choose substrings $S[1, 2]$ and $S[3, 5]$. ### Example Input 2 ``` 25 atcodercodeforcescodechef ``` ### Example Output 2 ``` 76 ```Author: | mrkerim |
Editorial | https://discuss.codechef.com/problems/PLANT |
Tags | deadwing97, hard, ltime78, mrkerim, strings, suffix-array, suffix_automata |
Date Added: | 23-11-2019 |
Time Limit: | 6 sec |
Source Limit: | 50000 Bytes |
Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS |
Comments
- Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. |
