[자료구조] 스트링 타입, 스트링 패턴 매치(KMP 알고리즘), 실패함수

스트링 추상 데이터 타입

문자열(string)

\(S = s_{0}, s_{1}, ... , s_{n-1}\)의 형태

- \(s_{0}\): 문자 집합의 원소

- n = 0: 공백 또는 널 문자열

 

연산

- 새로운 공백 문자열 생성

- 문자열 읽기, 출력

- 문자열 연결(concatenation)

- 문자열 복사

- 문자열 비교

- 서브스트링을 스트링에 삽입

- 스트링에서 서브스트링 삭제

- 스트링에서 특정 패턴 검색

 

class String
{
public:
  String(char *init, int m);
  // m의 길이로 문자열을 초기화하는 생성자
  
  bool operator==(String t);
  // 문자열 비교
  
  bool operator!();
  // 문자열이 비어 있으면 true, 그렇지 않으면 false 반환
  
  int Length();
  // 문자열의 길이 반환
  
  String Concat(String t);
  // *this뒤에 t연결해 반환
  
  String Substr(int i, int j);
  // 위치 i, i+1, ...에서 *this 문자가 포함된 문자열을 반환
  // i+j-1이 *this의 유효한 위치인 경우에는 예외를 던짐
  
  int Find(String pat);
  // pat이 시작하는 *this의 하위 문자열과 일치하도록 인덱스를 반환
  // 위치 i에서 pat이 비어 있거나 *this의 하위 문자열이 아닌 경우 -1을 반환
};

 

스트링 패턴 매치

• 두 개의 스트링 s와 pat 
• pat이 s에서 탐색할 패턴
• 호출형식: s.Find(pat)
• pat과 i번째 위치에서 시작하는 s의 부분문자열 부합될 때 인덱스 i를 반환
• pat이 공백이거나 s의 부분문자열이 아닌 경우 -1을 반환
• LengthP: 패턴 pat의 길이
• LengthS: 스트링 s의 길이
• s에서 위치 LengthS-LengthP의 오른쪽은 pat과 매치될 문자가 충분하지 않으므로 고려하지 않아도 됨

int String::Find(String pat)
{
    for (int start = 0; start <= Length() - pat.Length(); start++)
    { // str[start]부터 패턴 탐색
        for (int j = 0; j < pat.Length() && str[start + j] == pat.str[j]; j++) 
        // 패턴의 문자가 일치할 때 마다 j값 1씩 증가
            if (j == pat.Length() - 1) // pat 패턴 끝까지 일치하면
                return start;      // pat문자열이 시작하는 str의 인덱스 반환
    }
    return -1; // pat가 0이거나 pat 패턴이 s에 존재하지 않을시
}

 

시간복잡도 - O(LengthP · LengthS)

 

스트링 패턴 매치(KMP 알고리즘)

int String::FastFind(String pat)
{ // pat이 str의 서브스트링인지 구분
    int posP = 0, posS = 0; // pat, str에서 작업할 위치
    int lengthP = pat.Length(), lengthS = Length(); // 두 문자열의 길이 추출
    while ((posP < lengthP) && (posS < lengthS))
    {
        if (pat.str[posP] == str[posS]) // 문자를 비교
        {                               // 문자가 같을 경우
            posP++;
            posS++;
        }
        else if (posP == 0)
            posS++;
        else
            posP = pat.f[posP - 1] + 1; 
    // 패턴 매칭에 실패한 문자의 이전 문자가까지가 또 다른 패턴을 이루고 있을 수도 있으니
    // 이전 문자가 또 다른 패턴의 몇 번째 패턴인지를 조사해서 그 지점부터 다시 패턴매칭을
    // 시작할 수 있도록 함
    }
    if (posP < lengthP) // pat 패턴이 str에 존재하지 않음
        return -1;
    else                // pat 패턴이 str에서 시작하는 위치 리턴
        return posS - lengthP;
}

 

시간복잡도 - O(LengthP + LengthS)

 

FastFind 부분 - O(LengthP)

실패함수(f) - O(LengthS)

 

실패함수

f(failure function) 정의

• 제일 큰 k: k < j이며, \(p_{0} ... p_{k} = p_{j-k} ... p_{j}\)인, k ≥ 0가 존재하는 경우
• -1: 그 외의 경우

pat = abcabcacab의 경우
위: j / 중간: pat / f: 아래

0	1	2	3	4	5	6	7	8	9
a	b	c	a	b	c	a	c	a	b
-1	-1	-1	0	1	2	3	-1	0	1

pat = abaababaab의 경우

0	1	2	3	4	5	6	7	8	9
a	b	a	a	b	a	b	a	a	b
-1	-1	0	0	1	2	1	2	3	4

void String::FailureFunction()
{ // *this의 실패함수를 계산
    int lengthP = Length();
    f[0] = -1;
    for (int j = 1; j < lengthP; j++)
    { // for문 안에서 j값을 바꾸는 요소 없으므로 j는 1씩 계속 증가
      // for문 안에서 f[j] 값을 결정
        int i = f[j - 1]; // i는 for문에서 작업할 이전 단계 f값
        while ((*(str + j) != *(str + i + 1)) && (i >= 0))
            i = f[i];     // 비교하는 문자가 같지 않다면 i값 변경
        if (*(str + j) == *(str + i + 1))
            f[j] = i + 1;
        else
            f[j] = -1;
        // f[j] 값 결정
    }
}

 

시간복잡도 - O(LengthP)