'문장비교'에 해당되는 글 1건

ex) pos 8 deleted 4 chars "not "

- insertion : 추가된 문자와 그 위치 그리고 추가된 문자의 개수
            ex) pos 8 inserted 4 chars "not "

- change : 변경된 원래 문자와 새로운 문자 그 위치 그리고 원래 문자의 개수
            ex) pos 46 changed 10 chars from "thoroughly" to "anyway"
위치는 원래 문장을 기준으로 출력한다. 첫 번째 문자의 위치는 0으로 시작한다.

 

<Sample Input>
This is not a joke. This is life. Consider it thoroughly...
This is a joke. This is not life. Don't consider it anyway

<Sample Output>
pos 8 deleted 4 chars "not "
pos 28 inserted 4 chars "not "
pos 34 inserted 6 chars "Don't "
pos 46 changed 10 chars from "thoroughly" to "anyway"
(sample output을 보면 대소문자를 구분하지 않는다.)

문제에서 요구하는 것은 문장에서 삽입, 삭제, 변경의 정보를 알고 싶어하는 것이다. 거기에 추가적인 몇몇 정보를 원하는 것이다.
X에서 Y로 변경할 때 삽입, 삭제, 변경은 항상 일어나게 마련이고, 이러한 정보를 알아보는 가장 좋은 알고리즘은 Edit Distance를 이용하는 것이다.

그러나, 우리가 알고 있듯이 Edit Distance는 문자간의 정보를 알아보는 것이다.
즉, 아래와 같은 예시가 될 것이다.

본 문제는 단어간의 삽입, 삭제, 변경의 정보를 알고 싶어 하는 것이다.
즉, 이런 식이 될 것이다.

위 예시와 아래 예시의 차이점은 무엇인가?
눈에 보이는 차이점을 말하는 것이 아니라, 구현 상의 차이점을 말하는 것이다.

그렇다. 위 예시는 1차원 배열로 쉽게 해결이 되지만, 아래 예시는 2차원 배열로 해결해야 쉽다.
하나의 단어를 하나의 문자로 간주한다는 것은 사람의 생각으로는 쉽게 되지만, 막상 컴퓨터에 주입시키기 위해서는 한 단계를 더 거쳐야 하는 수고로움을 해야한다.


** 관련 글 **
Edit Distance (Edit Operations) using Dynamic Programming

** 소스 **