★조나단봉네 블로그★

Given two two strings, s1 and s2, write a program to check if s1 is a rotation of s2. But you can use strstr() only once. (abcdef = cdefab) 간단해 보이는데 방법이 잘 떠오르지 않았다. 침대에 엎드려서 생각해낸 방법으로 열심히 코딩을 한 후 답안을 확인해보니 2줄이면 끝난다. 내가 사용한 방법은 s1의 맨 끝단어(s1[n])와 맨 앞단어(s1[0])를 붙여서 이 문자열(t)이 s2에 존재하는 위치를 먼저 구한다. t가 s2에 존재하면 t가 존재하는 위치 뒷부분, s2의 맨 앞에서 t가 존재하는 부분 직전까지의 문자열이 각각 s1에 존재하는지를 적절하게 체크한다. 다만, t가 s2에 존재하지 않는 ..

Write a program to extract the longest repeated substring in a given string. 주어진 문자열에서 반복되는 가장 긴 문자열을 추출하자. 문자열의 길이를 n이라고 했을 때 가장 무식한 방법은 모든 가능한 문자열을 다 구해서 반복되는 문자열을 찾고 긴 문자열을 출력하면 된다. 비교 대상인 두 문자열의 시작점을 i, j라고하고 문자열의 길이를 k라고 하고, 비교할 수 있고 문자열을 비교하는 것 또한 k만큼 필요하므로 대략 O(n^4)이 나온다. 어쨌든, 좋지 않다. 이 문제에 접근하기 위해서 사용되는 것이 suffix array라는 것이다. 문자열에서의 각 시작점들의 인덱스를 값(element)으로 가지는 배열을 말한다. 말로 써놓으면 이해하기 어렵고 ..

C는 CS의 기초중에 기초라고 할 수도 있다. 하지만 C만 제대로 다 알아도 사실상 거의 다 안다고 할 수 있다. 컴프 마지막 숙제는 malloc과 free와 거의 동일한 기능을 하는 함수를 만드는 것인데 이게 사실 ANSI C 책에 그대로 나온다는 사실을 나중에 알았다. (누가 공개를 해버려서...) 문득 예전에 사 놓고 책꽂이에 쳐박혀 있던 이 책의 가치가 새삼스럽게 느껴진다. 책을 얼추 훑어보니 각종 기초 라이브러리에 대한 설명 및 구현 방법들이 있다. 예를 들면 printf는 어떻게 만들어져 있을까라든지 file I/O는 어떻게 하는 것인지... 무턱대고 쓸 줄만 알았지 사실 어떻게 구현되어 있는지는 잘 모르는게 사실이다. 문득 틈틈히 이 책부터 공부해야지... 하는 생각이 들었다. 몇 가지 기초..