[백준] 1701번 - Cubeditor / 골드 2 / 파이썬 풀이

문제 링크

https://www.acmicpc.net/problem/1701

1701번: Cubeditor

 

시간 제한 : 0.5 초

메모리 제한 : 128 MB

 

문제 요약

• 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열만 검색이 가능하게끔 하는 에디터.
  ex) abcdabc -> abc 는 검색 가능 / abcd는 한번만 나오므로 검색 불가.
• abcabcabc에서 abc는 세 번, abcabc는 두 번, abcabca는 한 번만 나오는 걸로 카운트.
  두 번 이상 나오는 문자열 중 길이가 가장 긴 것은 abcabc가 됨.
  
  
• 문제 : 두 번 이상 나오는 부분 문자열 중에서 길이가 가장 긴 문자열의 길이를 구하는 프로그램 작성.

 

입력

예제 입력1

abcdabcabb

예제 입력2

abcdefghijklmn

예제 입력3

abcabcabc

 

출력

예제 출력1

3

예제 출력2

0

예제 출력3

6

---

풀이

"팁 한마디"

def make_table(patten):
    length = len(patten)
    table = [0] * len(patten)		# pattern이라는 문자열에서 가장 긴 반복문자열의 길이를 저장하기 위한 table 선언
    j = 0
    for i in range(1, length):		# pattern의 길이만큼 for문 실행.
		# i를 1부터 시작함으로써, pattern에서의 두번째 문자부터 비교.
        while j > 0 and patten[i] != patten[j]:		# 반복문자열이 끝났음을 확인한다면
            j = table[j - 1]		# 반복문자열의 패턴 바로 전 인덱스부터 다시 j를 설정.
        if patten[i] == patten[j]:	
            j += 1
            table[i] = j	
    return max(table)


if __name__ == "__main__":
    s = input()		# 문자열 입력 받음
    result = 0

    for idx in range(len(s)):
        sub_str = s[idx:len(s)]		# idx라는 인덱스부터 시작하는 s의 부분 문자열 sub_str 선언
        result = max(result, make_table(sub_str))

    print(result)

 

참고

https://dirmathfl.tistory.com/308

https://peisea0830.tistory.com/65​

[Python 3] BOJ - 1701 "Cubeditor"