대표 이미지는 2021년 11월 27일 발매된 래퍼 쿤디판다의 정규 2집 'The Spoiled Child : 균'의 앨범 커버입니다.
길이가 2n+1인 문자열 af : a1a2a3...a2n+1과 역순인 ab : a2n+1a2na2n-1...a1이 있다. (n은 자연수)
어떠한 문자열 s : x1x2x3...xn와 i : i1i2i3...in, j : j1j2j3...jn(이 n은 위의 n과는 별개의 변수이다)를 정의하자. 이 세 문자열의 길이는 n이다.
이를 이용하여 집합 I(s), 함수 r(i, j)를 정의한다.
문자열 s에 관한 집합 I(s)={x1x2x3...xn, x2x3...xnx1, x3...xnx1x2, ...}
길이가 같은 문자열 i, j에 대한 함수 r(i, j) = 0(∃k(ik=jk)) or 1(￢∃k(ik=jk)) (k는 1 이상 n 이하의 자연수이다)
예로, 12345와 54321은 k=3에서 문자가 3으로 동일하므로 r(12345, 54321)=0이다. 하지만 r(1234, 4321)은 k가 몇이어도 문자가 다르므로 r(1234, 4321)=1이다.
I(ab)의 원소인 문자열 a에 대하여 r(af, ∀a)=0임을 증명하라.
좋아요
9
글쎄요
0
어려워요
2
-
보충설명: I(sn)을 다르게 설명하면, 문자열 snsnsnsn...의 모든 길이가 n인 부분입니다.
즉, sn=12345라면, I(sn)은 123451234512345...의 부분 중 길이가 5인 12345, 23451, 34512, 45123, 51234의 집합입니다.
r(12345, 54321)=0인 이유는 k=1에서 1, 5로 불일치, k=2에서 2, 4로 불일치, k=3에서 3, 3으로 일치, k=4에서 4, 2로 불일치, k=5에서 5, 1로 불일치하기 때문입니다.
즉, k=3에서 단 한번만 일치하더라도 r(12345, 54321)=0입니다. 다르게 말하면 r(444, 444)는 k=1, 2, 3에서 일치하지만 함숫값은 0입니다.
이를 이용해 문제를 쉽게 풀어 정리하자면,
'어떤 문자열이 있으면, 그 문자열의 역순을 계속 나열한 문자열에서 원래 문자열과 길이가 같은 어떠한 부분도 문자열과 같은 부분이 존재하는가?' 라고 생각할 수 있습니다.
-
해결
