충돌 문자열 프로그래밍 대회

Question

은 문자열의 집합을 감안할 때

ap*** 
ab*le 
a**** 
ab*** 

문제가 문자열의 집합 일치 여부, 문자열, 허용 차이의 수의 수를 주어진 찾을 수 있습니다 말한다.

위의 세트를 사용하면 일치하지 않는 단일 문자열 (두 번째 문자열)을 허용하는 경우 대답은 "예"이지만 일치하지 않는 문자열을 허용하지 않으면 "아니오"입니다.

어떤 알고리즘이 가장 좋으며 복잡도는 무엇입니까?

하나 하나의 해결책은 모든 조합을 살펴 보거나 간단히 잘못되었습니다. 예를 들어 **, ab 광고가 통과하기 때문에 문자열을 세트에 추가 할 수 없습니다 (별개의 "호환되지 않는"것으로 정의 됨). (에서)

실제 문제 : 문제 M

고고학자가 중요한 된 His torical 중요성 20 세기 텍스트 문서의 큰 컬렉션을 발견 한 2417 년. 중복 된 문서가 많았지 만, 시간이 많아서 텍스트의 대부분을 읽을 수 없게 만들었 기 때문에, 이라는 피해와 잘 맞지 않았 음을 분명히 알았습니다. 그 중 일부는 동의하지 않았습니다. 그러나 텍스트 그룹을 일관되게 만들 수 있음을 알았습니다. 즉, 텍스트 사이에 일치 성 (consistency)을 달성하려면 작은 수의 텍스트를 제외하여 달성 할 수있는 것으로 나타났습니다 (예 : ). 예를 들어, 텍스트 :

ap*** 
ab*le 
app*e 
*p\**e 

(*는 읽을 수없는 문자 임)은 두 번째 텍스트 만 제거하면 일관성을 유지할 수 있습니다.

입력은 일련의 텍스트로 구성됩니다. 각 세트는 집합의 텍스트 수와 제거 할 수있는 최대 텍스트 수를 지정하는 줄로 시작됩니다. 이것은 이고 줄마다 하나씩 개별 텍스트가옵니다. 각 텍스트는 소문자 또는 별표 중 적어도 하나 이상이고 250 자로 구성됩니다. 한 세트에있는 모든 텍스트는 동일한 길이가 이고 한 세트에 10,000 자 이하의 텍스트가 있습니다. 세트의 순서는 두 개의 0 (0 0)을 포함하는 행에 의해 종료됩니다.

각 세트의 출력은 에 따라 'Yes'또는 'No'중 하나를 포함하는 행으로 구성되며 지정된 수만큼의 텍스트를 제거하여 세트의 일관성을 유지할 수 있는지 여부를 나타냅니다.

Sample input 
4 1 
ap*** 
ab*le 
app*e 
*pple 
3 1 
a 
b 
c 
4 2 
fred 
ferd 
derf 
frd* 
0 0 

Sample output 
Yes 
No 
No 

Answer 1

이것은 숙제가되어서 몇 가지 세부 사항을 생략 할 것입니다.

trie은 매우 멋지게 처리 할 수 ​​있습니다. 주어진 텍스트에 *이 들어있는 모든 인덱스에서 해당 텍스트를 트라이의 다른 모든 리프에서 내려야합니다. 그런 다음 충분한 텍스트와 일치하는 터미널 노드를 찾기 위해 트라이를 걸 으면됩니다.

트라이에는 노드 수가 많으므로 n * m 노드가 있으므로 다른 텍스트를 추가하는 것은 O(nm)입니다.

트라이를 구축하는 데 복잡한 문제가 있습니다. 올바른 순서로 텍스트를 추가해야하며 각 텍스트 색인에 대해 올바른 순서를 확인해야합니다. 그렇지 않으면 ab에 대해 *b이 터미널 노드에 포함되어 있지 않은 상황이 발생할 수 있습니다. 하지만 그렇게하면 더 많은 알고리즘 복잡성이 발생하지 않습니다.

총 시간은 O(mn^2)입니다. 한번 구축 된 트라이를 걷는 것은 O(nm)이고 노드를 추가하는 것은 n 노드의 경우 O(nm)입니다.

Answer 2

문자열과 개수가 포함 된 일관된 문자열 집합을 표현할 것을 제안합니다. 문자열에는 집합에있는 문자열 중 하나에 문자가있는 위치에 문자가 있고 다른 문자에는 별표가 있습니다. count는 집합의 문자열 수입니다. 그래서 {ab **, a * b *} = [abb *, 2].

단일 표현으로 시작하여 [* *, 0]으로 시작하십시오.

당신이 문자열 X 볼 때마다 :

1) 추가 [X, 1]은 지금까지 표현의 일치 인 경우 표현

2)의 설정하려면 새로 만들기 문자열과 표현의 표현 - 카운트를 증가시키고, 필요한 경우 문자열에 더 많은 글자를 고칩니다. 새로운 표현을 표현 세트에 추가하십시오.

3) 동일한 문자열의 표현이 두 개 이상인 경우 하나만 유지하고 개수는 해당 문자열이있는 표현의 최대 개수로 유지하십시오.

4) 지금까지 본 문자열 수에서 제외 할 수있는 문자열 수를 뺀 수의 표현을 제거합니다.

5) - (1)이있는 경우 가장 그럴듯한 대답이 가장 큰 카운트 하나입니다 끝에 다음 문자열

과에서 반복합니다. 모든 일관된 응답이 작성됩니다. 한 번에 수작업으로 표현할 수있는 최대 수는 해당 단계에서 가능한 최대 답변 수입니다. Choose (n, x)는 N에서 그 지점에서 본 문자열 수이고 x는 현재 텍스트 수입니다. 버릴 수있다. x = 1이면 이것은 n (n-1)/2입니다. 이 작업을 n 번해야하고 다른 비용은 문자열의 길이 만 증가하므로 O (mn^3) 알고리즘이있는 것 같습니다.