some256   4년 전

가능한 광고의 길이 중 가장 짧은 길이를 N, W(A)를 A의 접두사와 접미사가 같으면서 가장 긴 non-trivial 문자열의 길이라고 하겠습니다.

Claim: |A| - W(A) = N

A - W(A) <= N 증명은 간단하므로 생략합니다.

만약 |B| < |A| 이고 A^inf = B*inf 인 문자열 B가 존재한다면

A^inf <= B^inf iff A <= B
A^inf >= B^inf iff A >= B

이나 |B| < |A| 이기 때문에 위 두 조건을 동시에 만족할 수 없으므로 모순입니다. 그러한 더 짧은 문자열 B는 존재하지 않습니다.

이와 비슷한 증명 문제로 도도의 수학놀이, 큰 수 만들기 문제 등이 있습니다.

dh0450   4년 전

제가 수학을 잘 모르는데, 길이가 무한한 문자열끼리 대소비교가 가능한가요?

댓글을 작성하려면 로그인해야 합니다.