Preparing NOJ

Beautiful Words

0ms 0K

Description:

You are given a string $$$A$$$ of length $$$N$$$ and a set $$$S$$$, containing $$$M$$$ strings.

A cyclic permutation $$$B_i$$$ of $$$A$$$, in which $$$i$$$ is between $$$1$$$ and $$$N$$$, is the string

$$$B_i = A_{i}A_{i+1} \dotsm A_{N-1}A_NA_1A_2 \dotsm A_{i-2}A_{i-1}$$$

and its score is defined as the maximum length of a substring of $$$B_i$$$ that is also a substring of some string in $$$S$$$.

A substring is defined as a contiguous sequence of letters. For example, ab and dc are substrings of abfdc, but ad and fc aren't substrings of abfdc.

Your task is to calculate the minimum score over all cyclic permutations of string $$$A$$$.

Input:

The first line contains two positive integers $$$N$$$ and $$$M$$$, ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 10^4$$$), representing the length of the string $$$A$$$ and the size of the set $$$S$$$, respectively.

The second line contains the string $$$A$$$.

Each of the next $$$M$$$ lines contains one string $$$s_i$$$, representing the $$$i$$$-th string in $$$S$$$.

All strings contain only lowercase English letters and it's guaranteed that the sum of lengths of all strings in $$$S$$$ never exceeds $$$10^5$$$ characters.

Output:

Output an integer representing the minimum score over all cyclic permutations of string $$$A$$$.

Sample Input:

7 3
acmicpc
acm
icpc
maratona

Sample Output:

3

Sample Input:

11 4
competition
oncom
petition
ztxvu
fmwper

Sample Output:

5

Sample Input:

12 4
latinamerica
zyvu
okp
wsgh
kqpdb

Sample Output:

0

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021-2022 ACM-ICPC Brazil Subregional Programming Contest

Code GYM103388B

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:23:24

Related

Nothing Yet