Module: 접두사 함수, Z 함수

Problem

코딩 이론에서 접두어가 없는 코드는 접두어가 아닌 단어 집합으로 자주 사용됩니다. α라는 단어는 β에서 α를 삭제하여 얻은 경우 β라는 단어의 접두사라고 합니다. 끝에 0개 이상의 문자가 있습니다. 예를 들어 a, ab 및 aba라는 단어는 aba라는 단어의 접두사입니다. 예를 들어 aba, aa 및 bac 단어 집합은 접두사가 없는 코드인 반면 abac 집합은 , aba, ba는 aba라는 단어가 abac라는 단어의 접두사이므로 존재하지 않습니다.

 Decipher 교수는 쓸모없는 정보 연구실에서 근무하며 접두사 코드에 대한 그의 새로운 발명을 연구합니다. 단어 집합에서 두 단어의 최대 공통 접두어 길이가 k를 초과하지 않는 경우 수준 k의 접두어가 거의 없는 코드라고 합니다. 예를 들어 집합 abac, abc, ba는 접두사가 거의 없는 수준 2 코드이고 집합 abac , abab, ba는 abac 와 abab 의 가장 긴 공통 접두어가 3이므로 존재하지 않습니다.

 Decifro 교수가 실험실 조교에게 설정한 다음 작업은 다음과 같습니다. 일련의 단어와 숫자 k가 주어지면 주어진 단어 중에서 선택해야 합니다. 접두어가 거의 없는 수준 코드 k인 최대 집합입니다. 귀하는 주니어 실험실 조교로서 해당 프로그램을 작성하도록 지정되었습니다.