형식적 언어 이론(formal language theory)과 컴퓨터 과학(computer science)에서, 부분문자열은 문자열(string) 내에서 문자(character)의 연속적인 수열입니다. 예를 들어 "the best of"는 "It was the best of times"의 부분문자열입니다. 대조적으로 "Itwastimes"는 "It was the best of times"의 부분수열이지만, 부분문자열이 아닙니다.
접두사(prefixes)와 접미사(suffixes)는 부분문자열의 특별한 경우입니다. 문자열 \(S\)의 접두사는 \(S\)의 시작에서 발생하는 \(S\)의 부분문자열입니다; 마찬가지로, 문자열 \(S\)의 접미사는 \(S\) 끝에서 발생하는 부분문자열입니다.
문자열 "apple"의 모든 부분문자열의 목록은 "apple", "appl", "pple", "app", "ppl", "ple", "ap", "pp", "pl", "le", "a", "p", "l", "e", ""입니다 (마지막에 빈 문자열에 주목하십시오).
Substring
문자열 \(u\)는 \(t = pus\)를 만족하는 두 문자열 \(p\)와 \(s\)가 존재하면 문자열 \(t\)의 부분문자열 (또는 인수)입니다. 특히, 빈 문자열은 모든 각 문자열의 부분문자열입니다.
예제: 문자열 \(u=\text{ana}\)는 둘의 다른 오프셋에서 \(t=\text{banana}\)의 부분문자열 (및 부분수열)과 같습니다:
첫 번째 발생은 \(p=\text{b}\)와 \(s=\text{na}\)로 얻어지고, 반면에 두 번째 발생은 \(p=\text{ban}\)와 빈 문자열인 \(s\)로 얻습니다.
문자열의 부분문자열은 문자열의 접미사의 접두사이고, 동등하게 접두사의 접미사입니다; 예를 들어, nan은 nana의 접두사이며, 이것은 차례로 banana의 접두사이며, 이것은 차례로 banana의 접미사입니다. 만약 \(u\)가 \(t\)의 부분문자열이면, 이것은 역시 부분수열(subsequence)이며, 이것은 보다 일반적인 개념입니다. 주어진 문자열에서 주어진 패턴의 발생은 문자열 검색 알고리듬(string searching algorithm)으로 찾아질 수 있습니다. 둘 이상의 문자열의 부분문자열과 같은 가장 긴 문자열을 찾는 것은 가장 긴 공통 부분문자열 문제(longest common substring problem)로 알려져 있습니다. 수학 문헌에서, 부분문자열은 역시 부분단어(subwords, 미국에서) 또는 인수(factors, 유럽에서)라고 불립니다.
Prefix
문자열 \(p\)는 만약 \(t = ps\)를 만족하는 문자열 \(s\)가 존재하면 문자열 \(t\)의 접두사입니다. 문자열의 적절한 접두사(proper prefix)는 문자열 자체와 같지 않습니다; 일부 출처는 게다가 적절한 접두사를 비-빈으로 제한합니다. 접두사는 부분문자열의 특별한 경우로 보일 수 있습니다.
예제: 문자열 ban은 문자열 banana의 접두사 (및 부분문자열과 부분수열)과 같습니다:
정사각 부분집합 기호는 때때로, \(p \sqsubseteq t\)가 \(p\)가 \(t\)의 접두사임을 나타내도록 접두사를 나타내기 위해 사용됩니다. 이것은 특정 종류의 접두사 순서(prefix order)인 접두사 관계(prefix relation)라고 불리는 문자열에 대한 이항 관계(binary relation)를 정의합니다.
Suffix
문자열 \(s\)는 \(t = ps\)를 만족하는 문자열 \(p\)가 존재하면 문자열 \(t\)의 접미사입니다. 문자열의 적절한 접미사는 문자열 자체와 같지 않습니다. 모다 제한된 해석은 그것이 역시 빈 것이 아니라는 것입니다. 접미사는 부분문자열의 특별한 경우로 보일 수 있습니다.
예제: 문자열 nana는 문자열 banana의 접미사 (및 부분문자열과 부분수열)과 같습니다:
문자열에 대해 접미사 트리(suffix tree)는 모든 그것의 접미사를 나타내는 트리(trie) 데이터 구조(data structure)입니다. 접미사 트리는 문자열 알고리듬(string algorithms)에서 많은 숫자의 응용을 가집니다. 접미사 배열(suffix array)은 알파벳순으로 정렬된 순서에서 접미사의 시작 위치를 나열하는 이 데이터 구조의 단순화된 버전입니다; 그것은 많은 같은 응용을 가집니다.
Border
테두리는 같은 문자열의 접미사와 접두사입니다. 예를 들어, "bab"은 "babab" (및 역시 "babooneatingakebab")의 테두리입니다.
Superstring
문자열의 유한 집합 \(P\)의 초월문자열은 \(P\)에서 모든 각 문자열을 부분문자열로 포함하는 단일 문자열입니다. 예를 들어, \(\text{bcclabccefab}\)은 \(P = \{\text{abcc}, \text{efab}, \text{bccla}\}\)의 초원문자열이고, \(\text{efabccla}\)는 더 짧은 초월문자열입니다. 일반적으로, 우리는 길이가 가능한 한 작은 초월문자열을 찾는 데 관심이 있습니다; 임의의 순서로 \(P\)의 모든 문자열의 연쇄는 \(P\)의 자명한 초월문자열을 제공합니다. 지정된 문자 집합의 모든 각 가능한 순열을 포함하는 문자열은 초월순열(superpermutation)이라고 불립니다.
References
- Lothaire, M. (1997). Combinatorics on words. Cambridge: Cambridge University Press. ISBN 0-521-59924-5.
- Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.
- Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.
