c언어 문자열 찾기 : strstr 함수로 손쉽게 찾아봅시다.

 strstr의 세부 구현은, 문자열 알고리즘을 하면서 차차 알아가도록 합시다. C언어에서, 어떤 문자열에서 특정한 문자열이 있는지 (패턴), 간단하게 찾기 위해서 strstr를 이용하면 좋습니다. 이 친구는 다음과 같이 씁니다.

 

 

char *strstr(const char *str,const char *pat);

 

 

 str 안에 pat이 있는지 찾습니다. 만약에 있다면, 찾은 최초의 위치를 리턴합니다. 그렇지 않다면 NULL을 리턴합니다. 예를 들어서 설명해 보겠습니다.

 

 

---

 저는 "chogahuigatrainlike"에서 "ga"를 찾으려고 합니다. 그러면 strstr은 어떤 것을 리턴할까요? char형 포인터를 리턴하니까, char형이 저장되어 있는 공간을 가리키는, 주솟값을 리턴할 건데요.

 

 

 str이 이런 식으로 있습니다. 여기서 "ga"를 찾을 건데요. 2군데에 있습니다.

 

 

 이 중에서 "ga"가 처음으로 출현한 곳은 연두색 부분입니다.

 

 

 그렇기 때문에, strstr 함수는 res의 주솟값, 그러니까 &(str[3])을 리턴합니다. 즉, "ga"가 처음 출현한 위치를 돌려줍니다. 아래 예제 프로그램을 봅시다.

 

 

 str이 "chogahuiga"입니다. 그리고, 저는 str에서 "ga"를 찾았습니다. 이 함수가 리턴하는 값은 "ga"가 처음 출현한 위치인, &(str[3])입니다. 3번째 요소라고 보시면 편해요. 그렇기 때문에, 7번째 줄의 출력 결과는 gahuiga가 나옵니다. 3번째 요소부터 문자열 끝까지 출력했기 때문입니다.

 

 만약에, 패턴이 없으면 NULL값을 리턴합니다. 예를 들어서, "gt26cw"라는 키워드는 str에서 찾을 수 없어요.

 

 

 즉, 이 프로그램을 실행시키면 if문에 걸리지 않고 else문에 걸립니다.

 

 

 따라서, ... is not founded in str이 출력됩니다.

 

 

---

 사실, string에서 pat이 있는지 함수 하나만 이용해서 손쉽게 찾을 수 있어요. 굉장히 실용적입니다. 그런데 말입니다. 조금 더 ps적인 예제 없을까요? 백준 사이트의 1543번, 문서 검색 문제는 string에 pat이 최대 몇 번 등장하느냐를 묻는 문제입니다. 단, 조건이 하나 있습니다. 찾은 단어들은 overlap이 되지 않아야 합니다.

 

 예를 들어서, str이 "abababa"이고, pat이  "aba"라고 생각해 봅시다.

 

 

 그러면 0번째에서도 "aba"를 찾을 수 있고, 2번째에서도 "aba"를 찾을 수 있어요. 그런데 둘은 겹쳐요. 그래서, 이 때는 겹치게 찾은 거에요. overlap이 된 거죠. 그런데, 4번째에서도 "aba"를 찾을 수 있는데요.

 

 

 두 개가 서로 겹치지 않아요. 따라서, 이 때는 valid하게 찾은 거에요. 이런 문제는 어떻게 풀면 좋을까요? 문자열 찾기 함수인 strstr을 이용하면 매우 손쉽게 풀 수 있는데요. 직관적으로 보았을 때, 맨 처음에는 &(str+0)부터 찾는 게 이득입니다. 그리고 나서 어떻게 하면 좋을까요?

 

 

 제가 칠한 노란색 부분에서 "aba"를 찾으면 될 겁니다. 그런 식으로 찾으면 최적인 것을 증명할 수 있어요. 이걸 어떻게 구현을 하느냐가 문제인데요.

 

 

 pos는 "aba"를 찾은 최초의 위치를 리턴합니다. 만약에 NULL값이 아닌 경우에는, pos를 pos+len으로 갱신해 버리면 됩니다. 그리고 계속 strstr의 리턴값이 NULL인지 아닌지 확인을 하면 좋겠네요.

 

 

 생각보다 간단하네요. 사실 for문을 이용하면, 코드를 더 줄일 수도 있겠네요.