[C] 문자열 다루기::문자열 검색

문자열 검색 기능은 실제론 많이 사용해 본적이 없다.

 

그러나 다음에 구현해 볼 문자열 토큰함수를 위해 미리 구현해야 한다.

---

구현에 앞서 잠깐 설계를 해보자면

 

source가 될 문자열과 해당 문자열에서 찾을 문자 혹은 문자열 target, 을 입력하고

 

반환값으로 source에 target이 얼마나 포함되어있는지와 포함되어있는 인덱스들을 함께

 

정수형 배열로 반환할 것이다.

 

함수 기능	문자열에서 특정 문자열의 위치를 찾아내는 함수
입력값	source(문자열), target(문자열)
반환값	정수형 배열
	일치하는 위치 수, 각 위치들

 

 

---

함수를 선언해준다

int* f(char* Src, char* Target) { 
    return NULL;
}

 

반환할 정수형 배열의 크기는 1 + n인데 ( n: 문자열이 일치된 위치들, 1: 문자열이 일치된 횟수 )

n을 찾기 위해선 문자열 일치 횟수를 찾는 것이 선행되어야한다.

 

이는 곧 문자열이 일치된 위치를 저장하기 위한 배열의 동적할당을 위해 먼저 문자열이 일치되는 횟수를 찾는

아주 불필요한 작업이 반복되므로 동적할당 메모리를 수시로 할당할 수 있는 realloc()을 사용하도록 하겠다.

 

    int arySize = 1;
    int* result = (int*)malloc(sizeof(int)*arySize);
    int idx = 0;
    
    int srcSize = StringLength(Src);
    int trgSize = StringLength(Target);

    for (int i = 0; i + trgSize < srcSize;) {
        // 문자열의 일치 확인
        for (int j = 0; ; i++) {             
            result = (int*)realloc(result, sizeof(int) * (++arySize));
            result[++idx] = i;
        }
    }
    
    return result;

다음과 같이 source 문자열을 반복하면서 문자열의 일치가 발생할 때마다

배열을 동적으로 추가할당하여 인덱스를 저장하면 되겠다.

 

 

// 문자열의 일치 확인
        for (int j = 0; ; j++) {

            // 문자열이 끝까지 일치한 경우
            if (Target[j] == 0) {
                result = (int*)realloc(result, sizeof(int) * (++arySize));
                result[++idx] = i;

                i += trgSize;
                break;
            }

            // 문자열이 일치하지 않은 경우
            if (Src[i+j] != Target[j]) {
                if (j == 0) i++;
                else i += j;
                break;
            }

        }

안에 문자열이 일치하는지 확인하는 조건문을 수정만 해주면 되겠다.

 

앞서 비교함수를 구현했는데 왜 굳이 또 구현했냐고 할 수 있는데

 

< 한번 비교된 부분은 그냥 넘어간다 >

이미 한번 비교해 본 부분은 다시 비교해볼 필요가 없기 때문에 효율적이다.

이를 위해서 굳이 한번 더 구현했다.

 

 

마지막으로 배열의 맨 앞에 일치항목이 몇개 있는지 넣어주면 되겠다.

    result[0] = arySize - 1;

 

함수 이름을 이쁘게 지어준 최종 코드는 다음과 같다.

int* StringFinder(char* Src, char* Target) { 
    int arySize = 1;

    int* result = (int*)malloc(sizeof(int)*arySize);

    int idx = 0;
    
    int srcSize = StringLength(Src);
    int trgSize = StringLength(Target);

    
    for (int i = 0; i + trgSize <= srcSize;) {
        
        // 문자열의 일치 확인
        for (int j = 0; ; j++) {

            // 문자열이 끝까지 일치한 경우
            if (Target[j] == 0) {
                result = (int*)realloc(result, sizeof(int) * (++arySize));
                result[++idx] = i;

                i += trgSize;
                break;
            }

            // 문자열이 일치하지 않은 경우
            if (Src[i+j] != Target[j]) {
                if (j == 0) i++;
                else i += j;
                break;
            }

        }
    }
    result[0] = arySize - 1;
    
    return result;
}

이 함수가 정상 작동하는지는 직접 테스트해보길 바란다