[코딩 테스트] 18일차: 문자열 알고리즘

문자열 알고리즘

문자열 알고리즘은 문자열을 처리하고 검색하는 데 사용됩니다. 이번 글에서는 문자열 검색 알고리즘인 KMP와 Rabin-Karp, 문자열 정렬, 그리고 다중 패턴 검색 알고리즘인 아호-코라식(Aho-Corasick)에 대해 알아보겠습니다.

KMP 알고리즘 (Knuth-Morris-Pratt)

KMP 알고리즘은 문자열 검색 알고리즘으로, 부분 일치를 이용하여 불필요한 비교를 줄여 검색 속도를 향상시킵니다.

 

예제: KMP 알고리즘 구현

JavaScript

function kmpSearch(text, pattern) {
  const lps = buildLPSArray(pattern);
  let i = 0; // text index
  let j = 0; // pattern index

  while (i < text.length) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }

    if (j === pattern.length) {
      return i - j; // match found
    } else if (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return -1; // no match found
}

function buildLPSArray(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length !== 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

const text = "abxabcabcaby";
const pattern = "abcaby";
console.log(kmpSearch(text, pattern)); // 6

Python

def kmp_search(text, pattern):
    lps = build_lps_array(pattern)
    i = 0 # text index
    j = 0 # pattern index

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == len(pattern):
            return i - j # match found
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return -1 # no match found

def build_lps_array(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    return lps

text = "abxabcabcaby"
pattern = "abcaby"
print(kmp_search(text, pattern)) # 6

Rabin-Karp 알고리즘

Rabin-Karp 알고리즘은 해시를 이용하여 문자열을 검색하는 알고리즘입니다. 주어진 텍스트의 부분 문자열과 패턴의 해시 값을 비교하여 일치 여부를 판단합니다.

 

예제: Rabin-Karp 알고리즘 구현

JavaScript

function rabinKarp(text, pattern, prime = 101) {
  const m = pattern.length;
  const n = text.length;
  const d = 256; // number of characters in the input alphabet
  let p = 0; // hash value for pattern
  let t = 0; // hash value for text
  let h = 1;

  // The value of h would be "pow(d, M-1)%q"
  for (let i = 0; i < m - 1; i++) {
    h = (h * d) % prime;
  }

  // Calculate the hash value of pattern and first window of text
  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % prime;
    t = (d * t + text.charCodeAt(i)) % prime;
  }

  // Slide the pattern over text one by one
  for (let i = 0; i <= n - m; i++) {
    // Check the hash values of current window of text and pattern
    if (p === t) {
      // Check for characters one by one
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) {
        return i; // match found
      }
    }

    // Calculate hash value for next window of text
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + 1)) % prime;

      if (t < 0) {
        t = (t + prime);
      }
    }
  }

  return -1; // no match found
}

const text = "abxabcabcaby";
const pattern = "abcaby";
console.log(rabinKarp(text, pattern)); // 6

Python

def rabin_karp(text, pattern, prime=101):
    m = len(pattern)
    n = len(text)
    d = 256 # number of characters in the input alphabet
    p = 0 # hash value for pattern
    t = 0 # hash value for text
    h = 1

    # The value of h would be "pow(d, M-1)%q"
    for i in range(m - 1):
        h = (h * d) % prime

    # Calculate the hash value of pattern and first window of text
    for i in range(m):
        p = (d * p + ord(pattern[i])) % prime
        t = (d * t + ord(text[i])) % prime

    # Slide the pattern over text one by one
    for i in range(n - m + 1):
        # Check the hash values of current window of text and pattern
        if p == t:
            # Check for characters one by one
            match = True
            for j in range(m):
                if text[i + j] != pattern[j]:
                    match = False
                    break
            if match:
                return i # match found

        # Calculate hash value for next window of text
        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % prime

            if t < 0:
                t = t + prime

    return -1 # no match found

text = "abxabcabcaby"
pattern = "abcaby"
print(rabin_karp(text, pattern)) # 6

문자열 정렬

문자열 정렬은 사전 순으로 문자열을 정렬하는 과정입니다. 자주 사용되는 방법으로는 기본 정렬 알고리즘을 이용하거나, 정렬 기준을 직접 설정하는 방법이 있습니다.

 

예제: 문자열 정렬 구현

JavaScript

function sortStrings(arr) {
  return arr.sort();
}

const strings = ["banana", "apple", "cherry"];
console.log(sortStrings(strings)); // ["apple", "banana", "cherry"]

Python

def sort_strings(arr):
    return sorted(arr)

strings = ["banana", "apple", "cherry"]
print(sort_strings(strings)) # ["apple", "banana", "cherry"]

아호-코라식(Aho-Corasick) 알고리즘

아호-코라식 알고리즘은 다중 패턴 검색 알고리즘으로, 여러 개의 패턴을 동시에 검색하는 데 사용됩니다. 트라이(Trie)와 실패 함수(Failure Function)를 이용하여 구현됩니다.

 

예제: 아호-코라식 알고리즘 구현

JavaScript

class AhoCorasick {
  constructor(patterns) {
    this.trie = {};
    this.output = {};
    this.fail = {};
    this.buildTrie(patterns);
    this.buildFailLinks();
  }

  buildTrie(patterns) {
    for (let pattern of patterns) {
      let node = this.trie;
      for (let char of pattern) {
        if (!node[char]) {
          node[char] = {};
        }
        node = node[char];
      }
      node.pattern = pattern;
    }
  }

  buildFailLinks() {
    const queue = [];
    for (let char in this.trie) {
      this

.fail[char] = this.trie;
      queue.push(this.trie[char]);
    }

    while (queue.length > 0) {
      let node = queue.shift();
      for (let char in node) {
        if (char === "pattern") continue;
        let fail = this.fail[node];
        while (fail && !fail[char]) {
          fail = this.fail[fail];
        }
        if (fail) {
          this.fail[node[char]] = fail[char];
          if (fail[char].pattern) {
            node[char].pattern = node[char].pattern || fail[char].pattern;
          }
        } else {
          this.fail[node[char]] = this.trie;
        }
        queue.push(node[char]);
      }
    }
  }

  search(text) {
    let node = this.trie;
    const result = [];
    for (let i = 0; i < text.length; i++) {
      const char = text[i];
      while (node && !node[char]) {
        node = this.fail[node];
      }
      if (node) {
        node = node[char];
        if (node.pattern) {
          result.push({ pattern: node.pattern, index: i - node.pattern.length + 1 });
        }
      } else {
        node = this.trie;
      }
    }
    return result;
  }
}

const patterns = ["he", "she", "his", "hers"];
const text = "ahishers";
const ac = new AhoCorasick(patterns);
console.log(ac.search(text)); // [{ pattern: 'his', index: 1 }, { pattern: 'he', index: 4 }, { pattern: 'she', index: 3 }, { pattern: 'hers', index: 4 }]

Python

from collections import deque, defaultdict

class AhoCorasick:
    def __init__(self, patterns):
        self.trie = defaultdict(dict)
        self.output = {}
        self.fail = {}
        self.build_trie(patterns)
        self.build_fail_links()

    def build_trie(self, patterns):
        for pattern in patterns:
            node = self.trie
            for char in pattern:
                node = node.setdefault(char, {})
            node['pattern'] = pattern

    def build_fail_links(self):
        queue = deque()
        for char in self.trie:
            self.fail[char] = self.trie
            queue.append(self.trie[char])

        while queue:
            node = queue.popleft()
            for char, child in node.items():
                if char == 'pattern':
                    continue
                fail = self.fail[node]
                while fail and char not in fail:
                    fail = self.fail[fail]
                self.fail[child] = fail[char] if fail else self.trie
                if 'pattern' in self.fail[child]:
                    child['pattern'] = child.get('pattern', '') + self.fail[child]['pattern']
                queue.append(child)

    def search(self, text):
        node = self.trie
        result = []
        for i, char in enumerate(text):
            while node and char not in node:
                node = self.fail[node]
            if node:
                node = node[char]
                if 'pattern' in node:
                    result.append((node['pattern'], i - len(node['pattern']) + 1))
            else:
                node = self.trie
        return result

patterns = ["he", "she", "his", "hers"]
text = "ahishers"
ac = AhoCorasick(patterns)
print(ac.search(text)) # [('his', 1), ('she', 3), ('he', 4), ('hers', 4)]

연습 문제

문제 1: 주어진 문자열에서 특정 패턴의 시작 인덱스 찾기

주어진 문자열에서 특정 패턴의 모든 시작 인덱스를 찾는 프로그램을 작성하세요.

JavaScript

function findPatternIndices(text, pattern) {
  const indices = [];
  const lps = buildLPSArray(pattern);
  let i = 0; // text index
  let j = 0; // pattern index

  while (i < text.length) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }

    if (j === pattern.length) {
      indices.push(i - j); // match found
      j = lps[j - 1];
    } else if (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return indices;
}

function buildLPSArray(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length !== 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

const text = "ababcabcababc";
const pattern = "abc";
console.log(findPatternIndices(text, pattern)); // [2, 5, 10]

Python

def find_pattern_indices(text, pattern):
    indices = []
    lps = build_lps_array(pattern)
    i = 0 # text index
    j = 0 # pattern index

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == len(pattern):
            indices.append(i - j) # match found
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return indices

def build_lps_array(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    return lps

text = "ababcabcababc"
pattern = "abc"
print(find_pattern_indices(text, pattern)) # [2, 5, 10]

문제 2: 주어진 문자열에서 여러 패턴 검색하기

주어진 문자열에서 여러 패턴을 동시에 검색하는 프로그램을 작성하세요.

JavaScript

class AhoCorasick {
  // ... (이전 코드와 동일)
}

const patterns = ["ab", "abc", "bc"];
const text = "ababcabc";
const ac = new AhoCorasick(patterns);
console.log(ac.search(text)); // [{ pattern: 'ab', index: 0 }, { pattern: 'abc', index: 2 }, { pattern: 'bc', index: 3 }, { pattern: 'ab', index: 4 }, { pattern: 'abc', index: 5 }, { pattern: 'bc', index: 6 }]

Python

class AhoCorasick:
    # ... (이전 코드와 동일)

patterns = ["ab", "abc", "bc"]
text = "ababcabc"
ac = AhoCorasick(patterns)
print(ac.search(text)) # [('ab', 0), ('abc', 2), ('bc', 3), ('ab', 4), ('abc', 5), ('bc', 6)]

결론

이번 글에서는 코딩 테스트 준비를 위해 문자열 알고리즘에 대해 배웠습니다. 이를 통해 KMP, Rabin-Karp, 아호-코라식 알고리즘의 개념과 구현 방법을 익혔습니다. 다음 글에서는 탐욕 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!