Problemas
문서의 유사중복을 판별하기에 문서를 통째로 비교하는 것은 효율성도 낮고 효과적이지 못하기 때문에,
보통 문서에서 의미 있는 시그너처(Signature)들을 추출한 후, 각 문서들의 시그너처를 비교하여 문서 중복 여부를 판별한다.
두 문서가 서로 공유하는 문서 시그너처가 많을 수록 유사도가 높다고 할 수 있는데,
두 문서 사이의 유사도가 지정된 유사도 임계값 이상일 경우 중복으로 판별된다.
이 문제에서 유사도를 판별하는 식은 다음과 같다.
sim(A,B) = |A∩B|/|A∪B|
여기서 ∩는 교집합, ∪는 합집합을 의미하며,
A, B는 각각 다른 두 문서에서 추출된 시그너처들의 집합이며,
문서간 유사도는 시그너처 집합 A, B의 합집합의 원소 개수에 대한 교집합의 원소 개수의 비율로 계산한다.
Entrada
입력의 첫 번째 줄에는 유사도 임계값 R (0＜R≤1, R은 실수)과 고려할 문서의 개수 D (1＜D≤200)가 하나의 스페이스로 구분되어 주어진다. 다음 D줄에는 한 줄에 하나씩 하나의 문서를 대표하는 문서 시그너처 목록이 시그너처 개수 S (1 < S≤500)와 함께 주어진다. 시그너처들은 하나의 스페이스로 분리되어 주어지며, 하나의 시그너처는 알파벳과 콜론(‘:’)으로 이루어진 공백이 없는 하나의 스트링이다. 여기서 대소문자를 구분하지 않도록 한다.
한 문서 내에 같은 시그너처가 여러 번 추출될 수도 있다. 문제를 단순하게 하기 위해 문서에서 추출된 횟수는 고려하지 않고, 추출 여부만 고려하도록 한다. 즉, 동일한 시그니처 abc:ab aBc:ab가 존재할 경우 이는 abc:ab라는 하나의 시그니처가 존재한다고 가정한다. 시그너처 스트링 하나의 최대 길이는 50을 넘지 않는다
Salida
출력은 임계값 R 이상의 유사도를 보여 중복으로 판별된 모든 문서의 쌍을 출력한다. 부동소수점 오차는 소수점 이하 6자리 까지 같으면 같은 수로 본다.
문서는 입력된 순서대로 1번부터 번호를 부여하여, 중복으로 판별된 각 문서 쌍을 한 줄에 하나씩 출력한다. 출력 방식은 “A-B” (A < B, A와 B는 문서번호)와 같이 빠른 번호가 앞에 오도록 하고 하이픈(“-”)으로 연결하여 출력한다. 중복 문서 쌍이 여러 개인 경우 앞의 문서 번호가 빠른 문서 쌍을 먼저 출력하고, 앞의 문서 번호가 같은 경우 뒤의 문서 번호가 빠른 문서 쌍을 먼저 출력한다. 만약 중복으로 판별된 문서쌍이 없을 경우 NONE을 출력한다.
Ejemplo #1
0.3 4
3 case:problem wrong:order duplicated:signature
1 order:wrong
1 cASe:PrObLem
3 duplicated:signature duplicated:signature dummy:abc
1-3
Ejemplo #2
1.0 2
2 a:weeklong:campain the:south:Carolina
3 a:rally:kick a:weeklong:campain the:south:Carolina
NONE
Ejemplo #3
0.5 3
2 a:weeklong:campain the:south:Carolina
3 a:rally:kick a:weeklong:campain the:south:Carolina
2 a:weeklong:campain the:south:Carolina
1-2
1-3
2-3
Debes iniciar sesión para escribir código.