C 프로그램으로 문자열에서 접미사와 동일한 가장 긴 접두사 찾기

문제 개요

주어진 문자열에서 접두사이면서 동시에 접미사인 가장 긴 부분 문자열의 길이를 구하는 문제입니다. 예를 들어 문자열 "abcab"의 경우, "ab"는 길이가 2이며 접두사와 접미사가 동일한 가장 긴 부분 문자열입니다.

입력 및 출력 예시

Input: str[] = { "aabbccdaabbcc" }
Output: 6
Input: abdab
Output: 2

접근 방법

문자열의 시작과 끝에서 각각 포인터를 출발시키면 어느 시점에 서로 겹쳐 정상적인 비교가 불가능해집니다. 따라서 문자열을 중간부터 나누어 왼쪽(접두사)과 오른쪽(접미사)을 매칭하는 방식을 사용합니다. 두 문자열이 일치하면 해당 길이를 반환하고, 일치하지 않으면 양쪽 모두 더 짧은 길이로 다시 시도합니다.

알고리즘

int longest(char str[], int n)
START
STEP 1 : DECLARE length AS 0 AND i AS n/2
STEP 2 : IF n < 2 THEN
    RETURN 1
STEP 3 : LOOP WHILE TILL str[i]!='\0'
    IF str[i] == str[length] THEN,
      INCREMENT length BY 1
      INCREMENT i BY 1
    ELSE
      IF length == 0 THEN,
          INCREMENT i BY 1
      ELSE
          DECREMENT length BY 1
      END IF
    END IF
END WHILE
RETURN length
STOP

C 언어 구현 예제

#include <stdio.h>
int longest(char str[], int n){
    int length = 0, i = n/2;
    if( n < 2 )
       return 1;
    while( str[i]!='\0' ){
       // 접미사에서 접두사와 같은 문자를 발견하면
       // length와 i를 증가시켜 일치하는 접두사·접미사의 길이를 셉니다
       if (str[i] == str[length]){
           ++length;
           ++i;
       } else { // 접두사와 접미사가 일치하지 않는 경우
           if(length == 0)
              ++i;
           else
              --length;
       }
    }
    return length;
}
int main(int argc, char const *argv[]){
    char str[] = {"abccmmabcc"};
    int n = sizeof(str)/sizeof(str[0]);
    int length = longest(str, n);
    printf("Length = %d", length);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다:

Length = 4

문자열 "abccmmabcc"에서 접두사 "abcc"와 접미사 "abcc"가 서로 일치하므로, 조건을 만족하는 가장 긴 부분 문자열의 길이인 4가 출력됩니다.