아름다운 단어
시간 제한1초메모리 제한1024 MB
문자열 A와 문자열 집합 S가 주어질 때, A의 모든 순환 순열 중에서 S에 속한 문자열의 부분 문자열이면서 가장 긴 것의 길이의 최솟값을 구한다.
문제
길이가 N인 문자열 A와 M개의 문자열을 원소로 하는 집합 S가 주어진다.
1 ≤ i ≤ N인 i에 대해, A의 순환 순열 Bi는 다음과 같은 문자열이다.
Bi = AiAi+1···AN-1ANA1A2···Ai-2Ai-1
Bi의 점수는 Bi의 부분 문자열이면서 S의 어떤 문자열의 부분 문자열이기도 한 것 중 가장 긴 것의 길이로 정의한다.
부분 문자열은 연속한 글자들의 나열이다. 예를 들어 ab와 dc는 abfdc의 부분 문자열이지만, ad와 fc는 abfdc의 부분 문자열이 아니다.
문자열 A의 모든 순환 순열에 대한 점수 중 최솟값을 구하여라.
입력
첫째 줄에는 두 양의 정수 N과 M이 주어진다. (1 ≤ N ≤ 105, 1 ≤ M ≤ 104) 각각 문자열 A의 길이와 집합 S의 크기이다.
둘째 줄에는 문자열 A가 주어진다.
다음 M개의 줄에는 각각 S의 i번째 문자열 si가 하나씩 주어진다.
모든 문자열은 알파벳 소문자로만 이루어져 있으며, S에 속한 모든 문자열의 길이의 합은 105을 넘지 않는다.
출력
문자열 A의 모든 순환 순열에 대한 점수 중 최솟값을 정수로 출력한다.