String combinations - MarisaOJ: Marisa Online Judge

String combinations

Time limit: 1000 ms
Memory limit: 256 MB
Given a string $S$ and $n$ string $T_1, T_2,...,T_m$ Find the longest substring of $S$ that can be created using $T_1, T_2,...T_m$. One string can be used multiple times. ### Input - The first line contains an integer $n$. - The second line contains string $S$. - The next $n$ lines, the $i^{th}$ line contains string $T_i$. ### Output - Print the length of the longest substring can be formed from $T_1, T_2,...,T_m$. ### Constraints - $1 \le n , |S| \le 2000$. - $\sum{|T_i|} \le 10^5$. ### Example Input: ``` 3 abbac ac b a ``` Output: ``` 5 ```