페이지

2013년 11월 6일 수요일

shortest unique pattern( 최소 길이 문자열)

문자열들의 집합이 주어졌을 때, 한 문자열의 핵심 부분 문자열은 이 문자열의 부분 문자열이면서 다른 문자열들에 포함되지 않는 문자열 중 가장 짧은 것을 의미한다.

예를 들어, {zebra, bras, ebbs} 가 주어졌을때 각 명령어의 핵심 부분 문자열은 다음과 같다.
zebra : z
bras : as
ebbs : bs(bb도 가능)

[input]
파일의 첫 줄에는 테스트케이스의 수 C가 주어져 있다. 1<=C<=10
각 테스트 케이스의 첫 줄에 명령의 집합이 포함하고 있는 문자열의 개수 N이 주어진다. 2<=N<=1000
다음 N줄에는 영어 소문자로 된 문자열들이 한 줄에 하나씩 주어지며, 각 문자열의 길이 최대는 100이다. 또한 어떤 명령어도 다른 명령어의 부분 문자열이 아니다.

[output]
각 테스트 케이스 마다 첫 줄에 "Case# X"를 출력한다. X는 케이스의 번호.
각 케이스에 대해서 N줄에 각각 해당하는 명령어의 핵심 부분 문자열의 길이를 출력한다.

[example]
2
3
zebra
bras
ebbs
3
foobar
bard
for


Case# 1
1
2
2
Case# 2
2
1
2

풀이
각 문자열의 substring에 대해서 Tree를 만든다. 각 Node는 char를 가지고 hitCount를 가지게 한다. 그래야 hitCount로 unique한지 판단이 가능하니까

ebbs를 예를 들면
ebbs의 substring은 아래와 같고
ebbs
bbs
bs
s
이를 바탕으로 Tree를 만들면
e
  b
    b
      s
b
  s
  b
    s
s
가 된다.

이렇게 모든 문자열의 substring에 대해서 Tree를 만들고
hitCount가 1인 node를 검색하면 unique한 substring을 검색 할 수 있다.

실제 구현은 여기에서.. (여기에 버그가 있는것 같은데 못찼겠음.--;; )
https://github.com/nberserk/codejam/blob/master/src/stop/july13/ShortestUniquePattern.java