이 경쟁 프로그래밍 질문은 간단한 정규 표현식으로 해결할 수 있습니다!

문제

ICPC Indonesia National Contest (INC) 2014, Problem H에서 수정됨

누군가 그의 페이스북 담벼락에서 외치고 있다.



폭언에는 파란색 텍스트가 여러 개 있습니다(해시 문자/#로 시작하므로 해시태그임). 단, #)(* , #*C) , ##CM 등 해시태그로 카운트되지 않는 모든 해시 시작 단어 및 텍스트는 아닙니다(텍스트의 #CM 부분만 하나로 간주).

유효한 해시태그(이 경우 이 문제에 대한 답변 지침)는 해시 문자(#)로 시작하고 알파벳(a-z, A-Z)과 선택적으로 (하나 이상의) 영숫자 문자 집합(a-z)이 뒤따라야 합니다. , AZ, 0-9). 해시태그는 다른 해시태그 바로 다음에 오면 안 되므로 인접한 각 해시태그는 공백이나 영숫자가 아닌 문자로 구분해야 합니다.

무효: #1234 , #$1-13LL , #alpha#beta (#alpha만 유효), #%#{#[}#hello (#hello만 유효)

유효한: #t0D4y1L3aRnED , #alpha£#beta (#alpha 및 #beta 둘 다 별도의 것으로 간주됨)

T개의 테스트 사례(1 <= T <= 100)가 제공되고 각 사례에 대해 처리할 입력 문자열이 제공됩니다. "Case #X: A"형식으로 유효한 해시태그의 수를 출력합니다. 여기서 X는 1의 사례 번호이고 A는 유효한 해시태그의 수이며, 유효한 모든 해시태그를 줄 바꿈으로 구분하여 출력합니다( \n ). .

Regex 기반 솔루션

보다,

(#[A-Za-z][0-9A-Za-z]*)(#[A-Za-z][0-9A-Za-z]*){0,1}

이 정규식 패턴은 캡처 그룹을 활용하여 개별 해시태그를 감지합니다. 패턴은 다음과 같이 구성됩니다.

(< Capture Group 1 >)(< Capture Group 2 >){0,1}

첫 번째 캡처 그룹에는 다음 패턴이 포함됩니다.

#[A-Za-z][0-9A-Za-z]*

정규식에 익숙하다면 위의 패턴이 앞서 언급한 해시태그 규칙과 정확히 일치한다는 것을 분명히 이해할 수 있습니다.

시작 # ,

다음에 알파벳 문자 ( [A-Za-z] ),

그리고 마지막으로 임의(0 이상)의 영숫자 문자( [0-9A-Za-z]* )가 이어집니다.

두 번째 캡처 그룹은 단순히 첫 번째 캡처 그룹을 반복하며 #alpha#beta 와 같이 유효한 해시태그를 따르는 유효한 해시태그를 캡처하기 위한 것입니다. 그런 다음 {0,1} 가 전체 정규식 패턴에 추가되어 두 번째 그룹이 선택 사항이 되도록 하여 2847#helloworld:$24 와 같이 격리된 다른 유효한 해시태그를 계속 검색할 수 있습니다. 이것은 또한 #hello#to#the#world와 같은 문자열이 하나의 해시태그로 감지되는 것을 방지합니다. 규칙에 따라 문자열이 2개의 개별 항목( #hello 및 #the )으로 처리되어야 하기 때문입니다.

ICPC 및 INC와 같은 경쟁 프로그래밍 대회에서는 C, C++, Java 또는 Python으로 제출할 수 있습니다. 다행스럽게도 유효한 정규식 패턴을 찾으면 표준 정규식 라이브러리를 사용하여 C++, Java 및 Python 코드로 직접 구현할 수 있습니다. 원래 질문에 답하려면 첫 번째 캡처 그룹을 사용하여 결과를 가져오거나 추출해야 합니다. 그렇지 않으면 심사 시스템에서 오답으로 간주합니다.

결론

이 문제는 해시태그 계산 프로세스를 최적화하기 위해 특정 문자열 일치 알고리즘을 활용하는 등 여러 가지 방법으로 해결할 수 있다고 생각합니다. 그러나 많은 프로그래밍 언어에서 허용되는 한 줄짜리 정규식 패턴으로 이 문제를 해결할 수 있다는 것은 매우 흥미로운 일입니다. 원래 참가자가 이 문제에 대해 정규식 기반 솔루션이 가능하다는 것을 얼마나 빨리 깨달았는지 궁금합니다.