코스

문자열 알고리즘

KMP·트라이·접미사 구조·팰린드롬.

Level 1 → Level 8 52 아이템 19 문제 33 강의 0 확인 문제
코스 진행도 0%
0 / 52 아이템 완료
01
Level 1 · Beginner

Beginner

문자열 알고리즘 · Beginner 단계

0/10 완료
Lesson 문자열의 개념: 글자들의 배열 필수 8m 현재

문자열이란

문자열(string) 은 글자들을 순서대로 늘어놓은 것입니다. 앞 강의에서 문자가
곧 숫자(아스키 코드)임을 보았는데, 문자열은 그런 문자들을 이어 붙인 배열로
생각하면 됩니다. "cat"은 ['c', 'a', 't']라는 길이 3짜리 배열입니다.

프로그래밍에서 문자열을 다루는 방식은 크게 둘입니다.

  • 문자 배열(C 스타일, char s[]): 끝을 알리는 널 문자 '\0'으로 끝남.
  • 문자열 객체(C++의 std::string, 파이썬의 str): 길이를 스스로 알고,
    이어 붙이기·부분 문자열 같은 연산을 메서드로 제공.

대회에서는 특별한 이유가 없으면 문자열 객체를 씁니다. 안전하고 편합니다.

인덱스와 길이

문자열의 각 글자는 \(0\)번부터 번호가 매겨집니다(0-인덱스). 길이가 \(N\)이면
유효한 인덱스는 \(0\)부터 \(N-1\)까지입니다.

문자열:  b  a  n  a  n  a
인덱스:  0  1  2  3  4  5     (길이 6)

s[0]은 첫 글자 'b', s[5]는 마지막 글자 'a', s[6]은 범위 밖입니다.
이 마지막 인덱스 실수(off-by-one)가 문자열 버그의 절반을 차지합니다.

기본 연산 한눈에 보기

연산 뜻 C++ Python
길이 글자 수 s.size() len(s)
인덱싱 \(i\)번째 글자 s[i] s[i]
이어붙이기 두 문자열 연결 a + b a + b
비교 사전순 대소 a < b a < b
부분 문자열 잘라내기 s.substr(i, len) s[i:i+len]
탐색 위치 찾기 s.find(t) s.find(t)

작은 예제로 감 잡기

s = "programming" (\(N = 11\))에서:

  • s[0]은 'p', s[N-1]은 'g'.
  • s.substr(0, 4)(파이썬 s[0:4])는 "prog".
  • s.find("gram")은 \(3\) (부분 문자열이 시작하는 인덱스).
  • s + "!"는 "programming!".

복잡도 감각

  • 인덱싱 s[i], 길이 확인은 \(O(1)\).
  • 전체 순회, 비교, 탐색(단순)은 길이에 비례해 \(O(N)\).
  • 이어붙이기 주의: 루프 안에서 매번 s = s + c를 하면 매번 복사가 일어나
    최악 \(O(N^2)\)이 될 수 있습니다. 뒤에 붙이는 append(push_back/리스트 후 join)를
    쓰는 것이 핵심입니다.

정리

  • 문자열은 문자들의 0-인덱스 배열.
  • 길이 \(N\)이면 유효 인덱스는 \(0 \dots N-1\).
  • 길이·인덱싱·이어붙이기·비교·부분 문자열·탐색이 6대 기본 연산.
  • 반복 이어붙이기는 \(O(N^2)\) 함정 — append 방식을 쓴다.

다음 강의에서 C++/파이썬 구현 문법과 순회·뒤집기 등을 자세히 봅니다.

Lesson C++/Python 구현 — 연산·입력·순회 선택 8m

C++ std::string 다루기

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "banana";
    cout << s.size() << "\n";        // 6  (length()와 동일)
    cout << s[0] << " " << s.back() << "\n";  // b a  (첫 글자 / 끝 글자)
    s.push_back('!');                // 뒤에 한 글자 추가 -> "banana!"
    s += "??";                       // 문자열 이어붙이기 -> "banana!??"
    cout << s.substr(1, 3) << "\n";  // "ana"  (1번부터 3글자)
    cout << s.find("nan") << "\n";   // 2   (없으면 string::npos)
}

주요 멤버:

  • size() / length() — 길이(같은 값).
  • s[i], front(), back() — 글자 접근.
  • push_back(c), pop_back(), += — 뒤에서 추가/제거.
  • substr(pos, len) — 부분 문자열(길이 생략 시 끝까지).
  • find(t) — 첫 등장 위치, 없으면 string::npos.
  • insert, erase, replace — 중간 편집.

입력 받기: 단어 vs 한 줄

이 구분은 실수가 잦으니 꼭 기억하세요.

string w;
cin >> w;                 // 공백 전까지 "한 단어"만 읽음

string line;
getline(cin, line);       // 개행 전까지 "한 줄 전체"(공백 포함)를 읽음

cin >> n 뒤에 곧바로 getline을 하면, 앞서 남은 개행 '\n'을 먼저 읽어
빈 줄이 잡힙니다. cin >> n; cin.ignore(); 로 개행을 버리고 나서
getline을 하세요.

순회와 뒤집기

string s = "abc";
for (char c : s) cout << c;          // 범위 기반 순회
for (int i = 0; i < (int)s.size(); i++) cout << s[i];

reverse(s.begin(), s.end());         // "cba"
sort(s.begin(), s.end());            // 글자 사전순 정렬 -> "abc"

s.size()는 부호 없는 타입이라 i < s.size() 비교에서 int i와 섞이면
경고가 납니다. (int)s.size()로 캐스팅하거나 인덱스를 부호 없는 타입으로
두는 습관이 안전합니다.

파이썬 str 다루기

파이썬 str은 불변(immutable) 입니다. 글자를 바꾸려면 새 문자열을 만들거나
리스트로 바꿔 편집한 뒤 다시 합칩니다.

s = "banana"
print(len(s))        # 6
print(s[0], s[-1])   # b a   (음수 인덱스는 뒤에서부터)
print(s[1:4])        # ana   (슬라이스 [시작:끝), 끝 미포함)
print(s.find("nan")) # 2     (없으면 -1)
print(s[::-1])       # ananab  (뒤집기)
print("".join(sorted(s)))  # aaabnn

# s[0] = 'x'  ->  에러! str은 불변
lst = list(s); lst[0] = 'x'; s = "".join(lst)

한 줄 입력은 input()(개행 없이 한 줄), 여러 값은 input().split().

효율적 이어붙이기

큰 결과 문자열을 만들 때는 매번 +하지 말고 모아서 한 번에 합칩니다.

// C++: ostringstream 또는 미리 reserve 후 push_back
string res; res.reserve(n);
for (int i = 0; i < n; i++) res.push_back('a' + i % 26);

parts = []
for i in range(n):
    parts.append(chr(ord('a') + i % 26))
res = "".join(parts)      # 리스트에 모았다가 join -> O(N)

정리

  • C++ string은 가변, 파이썬 str은 불변.
  • 단어 입력(cin >>)과 줄 입력(getline)을 구분하고, 섞을 때는 ignore().
  • 뒤집기·정렬은 reverse/sort([::-1]/sorted).
  • 대량 이어붙이기는 append 후 join.
Lesson 심화·변형 — 접두/접미, 회문, 애너그램, 함정 선택 8m

부분 문자열과 접두사·접미사

많은 문자열 문제가 "부분 문자열/접두사/접미사" 개념 위에 세워집니다.

  • 부분 문자열(substring): 연속된 구간. "banana"의 s[1..3] = "ana".
  • 접두사(prefix): 맨 앞에서 시작하는 부분 문자열. "ban".
  • 접미사(suffix): 맨 뒤에서 끝나는 부분 문자열. "ana".
  • 부분 수열(subsequence): 순서만 유지하고 띄엄띄엄 골라도 됨. "bnn".

부분 문자열은 "연속", 부분 수열은 "연속이 아니어도 됨" — 이 둘을 혼동하면
문제를 완전히 잘못 풀게 됩니다.

회문(팰린드롬) 판별

앞뒤가 같은 문자열인지 확인하는 기본기입니다. 두 포인터로 \(O(N)\).

bool isPalindrome(const string& s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
    }
    return true;
}

def is_palindrome(s):
    return s == s[::-1]

문자열 비교의 세부

a < b는 사전순(lexicographic) 비교입니다. 앞에서부터 처음으로 다른
글자의 코드값을 비교하고, 한쪽이 다른 쪽의 접두사면 짧은 쪽이 앞섭니다
("ab" < "abc"). 이때 비교 기준은 아스키 코드이므로 대문자가 소문자보다
앞선다는 점(앞 단원)을 기억하세요.

변형 1: 문자 개수/애너그램

두 문자열이 같은 글자 구성을 갖는지(애너그램)는 빈도 배열로 \(O(N)\)에 판별합니다.

bool isAnagram(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    int cnt[26] = {0};
    for (char c : a) cnt[c - 'a']++;
    for (char c : b) if (--cnt[c - 'a'] < 0) return false;
    return true;
}

정렬해서 비교(sort 후 ==)해도 되지만 \(O(N \log N)\)이라, 빈도 배열이 더 빠릅니다.

변형 2: 부분 문자열 존재/치환

  • 존재 여부: s.find(t) != string::npos (파이썬 t in s).
  • 모두 치환: 표준 find 루프 또는 파이썬 s.replace(a, b).
  • 개수 세기: find를 위치를 옮겨 가며 반복. 겹치는 경우 다음 탐색 시작점을
    pos + 1로 둘지 pos + len(t)로 둘지에 따라 결과가 달라지니 문제 정의를
    확인하세요.
def count_overlapping(s, t):
    c, i = 0, s.find(t)
    while i != -1:
        c += 1
        i = s.find(t, i + 1)   # 겹침 허용: 한 칸만 전진
    return c

빠른 대량 검색이 필요하면 이후 단원의 KMP·트라이 등을 사용합니다. 여기서는
기본 도구의 정확한 사용법을 익히는 것이 목표입니다.

흔한 함정 정리

  • off-by-one: 마지막 인덱스는 \(N-1\). substr/슬라이스의 끝 인덱스 규칙 확인.
  • 불변 문자열 수정(파이썬): s[i]=..는 에러 — 리스트로 바꿔 편집.
  • getline 개행 잔여: cin >> 뒤 getline 전에 ignore().
  • 부분 문자열 vs 부분 수열 혼동.
  • 부호 없는 size() 와 int의 비교 경고/버그.

정리

  • 접두사·접미사·부분 문자열·부분 수열의 정의를 명확히 구분한다.
  • 회문·애너그램·부분 문자열 검색은 기본기이며 대부분 \(O(N)\) 또는 \(O(N\log N)\).
  • 사전순 비교는 아스키 코드 기반.
  • 인덱스 경계와 개행 처리, 불변성 함정을 항상 의식한다.
Practice problem 알파카컵 1회: F - 알파카의 끝없는 울음소리 선택 25m
A00006

알파카컵 1회: F - 알파카의 끝없는 울음소리

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 가장 긴 공통 부분 수열 (LCS) 2 선택 25m
R02029

가장 긴 공통 부분 수열 (LCS) 2

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Lesson 아스키 코드의 개념: 문자는 숫자다 필수 8m

아스키 코드란 무엇인가

컴퓨터는 글자를 그대로 저장하지 못합니다. 내부적으로는 모든 것이 숫자이므로,
각 문자에 고유한 정수 번호를 붙이기로 약속했습니다. 이 약속표가 바로
아스키 코드(ASCII, American Standard Code for Information Interchange) 입니다.

즉 'A'라는 글자는 사실 정수 \(65\)이고, 'a'는 \(97\)입니다. 문자를 숫자처럼
다룰 수 있다는 이 사실 하나가 문자열 문제 대부분의 출발점입니다.

꼭 알아야 할 코드 범위

전부 외울 필요는 없습니다. 아래 세 구간과, 몇 가지 규칙만 기억하면 됩니다.

문자 아스키 값
'\0' (널) 0
'\n' (개행) 10
' ' (공백) 32
'0' ~ '9' 48 ~ 57
'A' ~ 'Z' 65 ~ 90
'a' ~ 'z' 97 ~ 122

핵심 규칙은 두 가지입니다.

  • 연속성: 같은 종류의 문자는 코드가 연속합니다. 'A'+1 == 'B', '0'+7 == '7'.
  • 대소문자 차이 32: 'a' - 'A' == 32. 소문자가 대문자보다 정확히 32 큽니다.

이 규칙 덕분에 "몇 번째 알파벳인가", "이 숫자 문자의 값은 얼마인가" 같은 질문을
뺄셈 한 번으로 답할 수 있습니다.

문자는 곧 정수: 작은 예제

C++에서 char는 사실상 1바이트짜리 작은 정수형입니다. 그래서 산술 연산이
그대로 됩니다.

char c = 'C';
int code = c;          // 67  (자동으로 정수로 승격)
char next = c + 1;     // 'D'

예를 들어 문자열 "A1a"의 각 글자를 코드로 바꾸면 \(65, 49, 97\) 이 됩니다.
'1'이 \(1\)이 아니라 \(49\)라는 점에 주의하세요 — 이것이 초보자가 가장 많이
헷갈리는 부분입니다.

두 개의 핵심 공식

아스키 활용의 90%는 아래 "기준 문자를 빼는" 패턴입니다.

(1) 숫자 문자 → 실제 수

$$ \text{digit} = c - \texttt{'0'} $$

'7' - '0'은 \(55 - 48 = 7\). 여러 자리 수를 직접 파싱할 때 기본이 됩니다.

(2) 알파벳의 순번(0부터)

$$ \text{index} = c - \texttt{'a'} \quad(\text{또는}\ c - \texttt{'A'}) $$

'c' - 'a'는 \(2\). 빈도 배열 cnt[26]의 인덱스를 만들 때 거의 항상 쓰입니다.

복잡도

문자 하나를 숫자로 바꾸는 것은 \(O(1)\)이고, 길이 \(N\) 문자열을 한 번 훑으면
\(O(N)\)입니다. 아스키 자체가 비용을 만드는 일은 없습니다.

정리

  • 문자는 내부적으로 정수다(아스키 코드).
  • 숫자 문자는 \(48\)부터, 대문자는 \(65\)부터, 소문자는 \(97\)부터 연속한다.
  • 대소문자 차이는 \(32\).
  • 두 공식: 숫자값 c - '0', 알파벳 순번 c - 'a'.

다음 강의에서 이 규칙들을 실제 코드(빈도 배열, 대소문자 변환, 진법 변환)로
엮습니다.

Lesson 변환·빈도 배열·자리 파싱 구현 선택 8m

문자 ↔ 숫자 변환 (C++ / Python)

C++은 char가 곧 정수라 캐스팅만으로 오갑니다. 파이썬은 전용 내장 함수
ord(문자→코드)와 chr(코드→문자)를 씁니다.

char c = 'A';
int code = (int)c;      // 65
char back = (char)68;   // 'D'

print(ord('A'))   # 65
print(chr(68))    # 'D'

대소문자 변환

대소문자가 정확히 \(32\) 차이라는 사실을 그대로 씁니다. 다만 직접 \(\pm 32\)
하는 것보다 기준 문자로 정규화하는 편이 안전합니다.

char toLower(char c) {
    if ('A' <= c && c <= 'Z') return c - 'A' + 'a';
    return c;
}
char toUpper(char c) {
    if ('a' <= c && c <= 'z') return c - 'a' + 'A';
    return c;
}

표준 라이브러리를 써도 됩니다. <cctype>의 tolower, toupper,
isalpha, isdigit, isupper, islower가 있습니다. 다만 이 함수들은
인자를 int로 받으며 음수 char가 들어오면 미정의 동작이므로
tolower((unsigned char)c) 처럼 캐스팅하는 습관이 안전합니다.

print('a'.upper())     # 'A'
print('Z'.lower())     # 'z'
print('7'.isdigit())   # True

빈도 배열: 아스키의 대표 응용

문자를 인덱스로 바꿀 수 있으니, 등장 횟수를 세는 배열을 곧바로 만들 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "banana";
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;     // 문자 -> 0..25 인덱스
    // a:3, b:1, n:2
    for (int i = 0; i < 26; i++)
        if (cnt[i]) cout << char('a' + i) << ": " << cnt[i] << "\n";
}

s = "banana"
cnt = [0] * 26
for c in s:
    cnt[ord(c) - ord('a')] += 1
# 파이썬은 collections.Counter(s) 가 더 편하다

대문자·소문자·숫자가 섞이면 크기 \(128\)짜리 배열 cnt[128]을 만들고
cnt[(unsigned char)c]++ 로 코드값 자체를 인덱스로 쓰면 간단합니다.

자리 숫자 파싱

여러 자리 정수 문자열을 직접 숫자로 만드는 고전 패턴입니다.

string t = "1234";
int val = 0;
for (char c : t) val = val * 10 + (c - '0');   // 1234

역으로, 숫자 \(n\)의 각 자리를 문자로 출력할 때도 char('0' + digit)을 씁니다.

정리

  • 변환: C++은 캐스팅, 파이썬은 ord/chr.
  • 대소문자는 기준 문자로 정규화하는 편이 안전하고, 표준 tolower류는
    unsigned char로 캐스팅해서 넘긴다.
  • 빈도 배열은 c - 'a'(또는 코드값 그대로)를 인덱스로 삼는 아스키의 대표 응용.

다음 강의에서 흔한 함정과 진법 변환·정렬 같은 변형을 봅니다.

Lesson 심화·변형 — 함정, 대소문자 무시, 시저, 진법 선택 8m

흔한 함정

1. '1'은 \(1\)이 아니다. 문자 '1'의 코드값은 \(49\)입니다. 숫자로
쓰려면 반드시 '1' - '0'. 이 실수 하나로 답이 크게 어긋납니다.

2. char의 부호. C++ 표준은 char가 부호 있는지 없는지를 정하지
않습니다. 아스키 범위(\(0\sim127\))만 다루면 문제없지만, \(128\) 이상 바이트
(예: 한글 UTF-8 바이트)를 배열 인덱스로 쓰면 음수가 되어 범위를 벗어납니다.
항상 (unsigned char)c로 캐스팅하세요.

int cnt[256] = {0};
for (char c : s) cnt[(unsigned char)c]++;   // 음수 인덱스 방지

3. <cctype> 함수에 음수 전달. tolower(c), isdigit(c) 등에
음수 char를 넘기면 미정의 동작입니다. isdigit((unsigned char)c)로 감쌉니다.

4. 한글은 1바이트가 아니다. 아스키는 영문·숫자·기호만 다룹니다. UTF-8에서
한글 한 글자는 3바이트라 s.size()가 글자 수와 다릅니다. 한글 "글자 수"를
정확히 세려면 파이썬 str(유니코드 단위)이나 별도 처리가 필요합니다.

변형 1: 대소문자 무시 비교

한쪽으로 정규화한 뒤 비교하면 됩니다.

bool equalIgnoreCase(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    for (size_t i = 0; i < a.size(); i++)
        if (tolower((unsigned char)a[i]) != tolower((unsigned char)b[i]))
            return false;
    return true;
}

변형 2: 시저 암호(문자 회전)

알파벳을 \(k\)칸 미는 고전 문제. 기준 문자로 내려서 \(\bmod 26\) 회전 후 되올립니다.

char shift(char c, int k) {
    if ('a' <= c && c <= 'z') return 'a' + (c - 'a' + k % 26 + 26) % 26;
    if ('A' <= c && c <= 'Z') return 'A' + (c - 'A' + k % 26 + 26) % 26;
    return c;   // 알파벳이 아니면 그대로
}

k가 음수여도 되도록 + 26을 더해 항상 양수 나머지를 만드는 것이 요령입니다.

변형 3: 임의 진법의 한 자리

\(16\)진법 이상에서는 \(10\) 이상 자리를 A~F로 표기합니다. 코드값 규칙으로
숫자·문자를 한 번에 처리합니다.

int digitValue(char c) {          // '0'..'9','A'..'F' -> 0..15
    if ('0' <= c && c <= '9') return c - '0';
    if ('A' <= c && c <= 'F') return c - 'A' + 10;
    if ('a' <= c && c <= 'f') return c - 'a' + 10;
    return -1;
}
char digitChar(int v) {           // 0..15 -> '0'..'9','A'..'F'
    return v < 10 ? char('0' + v) : char('A' + v - 10);
}

변형 4: 문자 기준 정렬

문자열을 사전순으로 정렬하는 것은 결국 코드값 비교입니다. C++의 <,
파이썬의 기본 비교 모두 아스키(유니코드) 코드값을 씁니다. 그래서 대문자가
소문자보다 앞선다('Z'(90) < 'a'(97))는 점을 기억해야, "AbC"와 "abc"의
순서가 직관과 다를 때 당황하지 않습니다.

정리

  • 숫자 문자와 실제 수를 혼동하지 말 것.
  • 배열 인덱스로 쓸 때는 unsigned char로 캐스팅.
  • 대소문자 무시 비교, 시저 암호, 진법 변환은 모두 "기준 문자 빼고 더하기"의
    변형이다.
  • 사전순 정렬은 코드값 비교이며 대문자가 소문자보다 앞선다.
Practice problem 알파카컵 1회: F - 알파카의 끝없는 울음소리 선택 25m
A00006

알파카컵 1회: F - 알파카의 끝없는 울음소리

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 가장 긴 공통 부분 수열 (LCS) 2 선택 25m
R02029

가장 긴 공통 부분 수열 (LCS) 2

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
02
Level 2 · Solver

Solver

문자열 알고리즘 · Solver 단계

0/5 완료
Lesson 토큰·구분자와 형식 있는 입력의 개념 필수 8m

파싱이란

파싱(parsing) 은 정해진 형식으로 주어진 문자열을 의미 있는 조각(토큰)으로
쪼개어 원하는 값으로 바꾸는 일입니다. 알고리즘이라기보다 "입력을 정확히 읽는
기술"이며, 많은 문제에서 실제 난이도는 알고리즘이 아니라 입력 형식에
있습니다.

예를 들어 다음 세 가지는 모두 "파싱" 문제입니다.

  • "3 1 4 1 5" 처럼 공백으로 나뉜 여러 수 읽기
  • "2026-07-21" 에서 연·월·일 분리
  • "add 3, remove 5;" 같은 명령 형식 해석

토큰과 구분자

토큰(token) 은 의미 단위(수, 단어)이고, 구분자(delimiter) 는 토큰을
나누는 문자(공백, 쉼표, 콜론 등)입니다. 파싱의 핵심 질문은 두 가지입니다.

  1. 구분자가 무엇인가? (공백 하나? 여러 개? 쉼표? 줄바꿈?)
  2. 토큰을 어떤 타입으로 바꿀 것인가? (정수? 실수? 문자열 그대로?)

세 가지 상황과 도구

상황 C++ 도구 Python 도구
공백으로 나뉜 값들 cin >> input().split()
한 줄 전체(공백 포함) getline input()
특정 문자로 분리 getline(ss, tok, ',') s.split(',')
형식 문자열에서 값 추출 sscanf / stringstream 슬라이싱 / re

작은 예제

입력이 다음과 같다고 합시다.

3
Alice 90
Bob 85
Carol 77

첫 줄은 사람 수 \(N\), 이후 각 줄은 이름 점수입니다. 이는 "줄 수를 먼저 읽고,
각 줄에서 단어 하나 + 정수 하나"를 읽는 전형적 형식입니다. cin >> n 뒤
cin >> name >> score 를 \(N\)번 반복하면 끝납니다 — >> 가 공백/개행을
자동으로 건너뛰기 때문입니다.

반면 이름에 공백이 들어갈 수 있다면("Mary Jane 90") >> 만으로는 안 되고,
줄 전체를 읽어 마지막 공백 기준으로 점수를 떼어내는 파싱이 필요합니다.
입력 형식을 정확히 읽는 것이 왜 중요한지 보여 주는 예입니다.

언제 무엇을 쓰나

  • 값들이 공백/개행으로만 나뉘고 타입이 분명하면 → cin >> / split() 이 가장 간단.
  • 공백이 토큰 안에 들어갈 수 있거나 줄 단위 의미가 있으면 → getline 으로
    줄을 읽은 뒤 직접 분해.
  • 구분자가 특수문자(, : /)면 → stringstream + getline(.,.,delim) 또는
    파이썬 split(delim) / 정규식.

정리

  • 파싱 = 형식 있는 문자열을 토큰으로 쪼개 값으로 변환.
  • 먼저 "구분자"와 "목표 타입"을 정한다.
  • 공백 분리는 >>/split, 줄 단위는 getline, 특수 구분자는 stringstream/split(delim).

다음 강의에서 각 도구의 구체적 구현을 봅니다.

Lesson 구현 — cin/getline/stringstream, split·정규식 선택 8m

C++: cin >> 로 공백 분리 읽기

>> 는 앞쪽 공백·개행을 건너뛰고 다음 토큰 하나를 읽습니다. 개수를 모를 때는
while (cin >> x) 로 EOF까지 읽습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x;
    long long sum = 0;
    while (cin >> x) sum += x;   // 공백/개행 상관없이 모든 정수 읽기
    cout << sum << "\n";
}

C++: getline 으로 한 줄 읽기

공백을 포함한 줄 전체가 필요할 때 씁니다.

string line;
while (getline(cin, line)) {
    // line 에는 개행을 뺀 한 줄이 통째로 들어온다
}

주의(가장 흔한 버그): cin >> n 직후 getline 을 하면 앞줄에 남은 개행
'\n' 이 먼저 읽혀 빈 줄이 잡힙니다. 개행을 버리고 나서 읽으세요.

int n; cin >> n;
cin.ignore();                 // 남은 개행 하나 제거
string line;
getline(cin, line);           // 이제 진짜 다음 줄

C++: stringstream 으로 토큰 분리

읽어 온 한 줄을 stringstream 에 넣으면 >> 로 공백 토큰을, getline(ss,tok,delim)
으로 특정 구분자 토큰을 뽑을 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string line;
    getline(cin, line);              // 예: "3 1 4 1 5"
    stringstream ss(line);
    vector<int> nums; int v;
    while (ss >> v) nums.push_back(v);   // 공백 기준 정수들

    // 쉼표 구분: "apple,banana,cherry"
    string csv = "apple,banana,cherry", tok;
    stringstream cs(csv);
    vector<string> parts;
    while (getline(cs, tok, ',')) parts.push_back(tok);
}

getline(ss, tok, ',') 는 빈 토큰도 만들어 냅니다(예: "a,,b" → a, `,b). 연속 공백은>>` 가 알아서 건너뛰지만, 지정 구분자 분리는 빈 조각을 남긴다는
차이를 기억하세요.

C++: sscanf 로 형식 파싱

날짜·좌표처럼 형식이 고정돼 있으면 sscanf 가 간결합니다.

int y, m, d;
sscanf("2026-07-21", "%d-%d-%d", &y, &m, &d);   // 2026 7 21

Python: split 계열

파이썬은 대부분 split 하나로 끝납니다.

# 공백(여러 개 포함)으로 분리 + 정수 변환
nums = list(map(int, input().split()))

# 특정 구분자로 분리
parts = "apple,banana,cherry".split(",")       # ['apple','banana','cherry']

# 인자 없는 split() 은 연속 공백을 하나로 취급하고 양끝 공백 제거
"  a   b  ".split()        # ['a', 'b']
# 인자 있는 split(',') 은 빈 토큰 유지
"a,,b".split(",")          # ['a', '', 'b']

여러 줄을 한꺼번에 빠르게 읽으려면 sys.stdin:

import sys
data = sys.stdin.read().split()   # 모든 공백/개행 기준 토큰
it = iter(data)
n = int(next(it))
arr = [int(next(it)) for _ in range(n)]

Python: 정규식으로 복잡한 형식

구분자가 여럿이거나 불규칙하면 re 를 씁니다.

import re
s = "add 3, remove 5; add 7"
tokens = re.split(r"[,\s;]+", s.strip())     # ['add','3','remove','5','add','7']
nums = re.findall(r"-?\d+", s)               # ['3','5','7']  음수 포함

re.split(r"\s+", s) 처럼 여러 공백을, re.findall(r"-?\d+", s) 로 문자열
속 정수만 골라내는 두 패턴이 특히 자주 쓰입니다.

정리

  • 공백 분리: cin >> / split().
  • 줄 읽기: getline / input(), cin >> n 뒤에는 ignore().
  • 특수 구분자: stringstream+getline(.,delim) / split(delim)(빈 토큰 유지).
  • 형식 고정: sscanf / 파이썬 슬라이싱·정규식.
Lesson 실전 가이드 — 입력 형식이 곧 문제인 경우 선택 8m

실전 가이드 — 입력 형식이 곧 문제인 경우

파싱 문제에서 막히는 대부분은 알고리즘이 아니라 형식의 예외 상황입니다.
아래 체크리스트를 습관화하세요.

  • 값의 개수가 주어지는가, 아니면 EOF까지인가?
  • 구분자가 단일 공백인가, 여러 공백/탭인가, 특수문자인가?
  • 토큰 안에 공백이 들어갈 수 있는가?(이름, 문장)
  • 빈 줄·후행 공백·CRLF(\r) 가 섞여 있는가?
  • 음수·소수점·부호가 있는가?

함정 1: cin >> 와 getline 혼용

앞 강의에서 본 최대 함정입니다. 수를 >> 로 읽은 뒤 줄을 getline 으로 읽으면
빈 줄이 먼저 잡힙니다. cin.ignore()(또는 ignore(numeric_limits<streamsize>::max(), '\n'))
로 개행을 비운 뒤 읽으세요.

함정 2: 후행 캐리지 리턴 \r

윈도우에서 만든 입력은 줄이 \r\n 으로 끝납니다. getline 은 \n 만
제거하므로 줄 끝에 보이지 않는 '\r' 이 남아 비교가 어긋납니다.

if (!line.empty() && line.back() == '\r') line.pop_back();

line = input().rstrip("\r\n")   # 또는 line.rstrip()

함정 3: 지정 구분자 분리의 빈 토큰

getline(ss, tok, ',') 와 파이썬 split(',') 는 "a,,b" 를 세 조각
(a, 빈, b)으로 만듭니다. 빈 토큰이 의미 없다면 걸러내야 합니다.

parts = [p for p in s.split(',') if p]     # 빈 조각 제거

변형 1: 줄 끝 공백 개수가 다른 표 파싱

여러 공백으로 정렬된 표는 인자 없는 split()(파이썬) 또는 stringstream >>
(C++)로 처리하면 공백 개수에 상관없이 토큰만 얻습니다. 고정폭 컬럼이라면
substr/슬라이싱으로 위치를 잘라내는 편이 정확합니다.

변형 2: 중첩·복합 형식

"(1,2) (3,4)" 같은 형식은 (a) 괄호 쌍을 먼저 토큰화하고 (b) 안의 쉼표로
다시 쪼개는 2단계 파싱이 깔끔합니다. 정규식 \((-?\d+),(-?\d+)\) 로 한
번에 뽑을 수도 있습니다.

import re
pts = re.findall(r"\((-?\d+),(-?\d+)\)", "(1,2) (3,-4)")
# [('1','2'), ('3','-4')]
pts = [(int(a), int(b)) for a, b in pts]

변형 3: 큰 입력의 속도

수십만 줄 이상이면 입력 속도가 시간 초과를 부릅니다.

  • C++: ios::sync_with_stdio(false); cin.tie(nullptr); 를 main 첫 줄에.
  • Python: input() 대신 sys.stdin.readline 또는 sys.stdin.read() 로 한꺼번에.
ios::sync_with_stdio(false);
cin.tie(nullptr);

import sys
input = sys.stdin.readline    # 반복 input()보다 훨씬 빠름

변형 4: 직접 정수 파싱

stoi/atoi/int() 없이 문자열을 정수로 바꾸는 것은 앞 단원의 아스키
공식 그대로입니다. 부호와 공백을 먼저 처리합니다.

long long parseInt(const string& s) {
    int i = 0, sign = 1;
    while (i < (int)s.size() && s[i] == ' ') i++;
    if (i < (int)s.size() && (s[i] == '+' || s[i] == '-')) {
        if (s[i] == '-') sign = -1; i++;
    }
    long long v = 0;
    while (i < (int)s.size() && '0' <= s[i] && s[i] <= '9')
        v = v * 10 + (s[i++] - '0');
    return sign * v;
}

정리

  • 파싱의 난이도는 예외 처리(빈 토큰, \r, 개행 잔여, 여러 공백)에 있다.
  • 구분자 종류에 맞는 도구를 고르고, 빈 토큰 여부를 항상 확인한다.
  • 대량 입력은 빠른 입력 설정이 필수.
  • 복합 형식은 2단계 토큰화 또는 정규식으로 나눠 처리한다.
Practice problem 알파카컵 1회: D - 코딩 천재 알파카 선택 25m
A00004

알파카컵 1회: D - 코딩 천재 알파카

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Gold I 골드 I 지금 풀기
Practice problem 올바른 괄호의 값 선택 25m
R00773

올바른 괄호의 값

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Gold IV 골드 IV 지금 풀기
03
Level 4 · Challenger

Challenger

문자열 알고리즘 · Challenger 단계

0/5 완료
Lesson 접두사 트리의 구조 필수 8m

트라이란

트라이(trie, 접두사 트리) 는 여러 문자열의 집합을 글자 단위 트리로
저장하는 자료구조입니다. 루트에서 어떤 노드까지 내려가며 만나는 글자들을 이으면
하나의 접두사가 되고, 공통 접두사는 하나의 경로를 공유합니다.

예를 들어 {"cat", "car", "card", "dog"} 를 넣으면 cat 과 car, card 는
c → a 까지 경로를 공유합니다.

(root)
 ├─ c ─ a ─ t*        "cat"
 │         └ r* ─ d*   "car", "card"
 └─ d ─ o ─ g*        "dog"

* 는 그 지점에서 단어가 끝난다는 표시(종료 플래그)입니다.

무엇이 빠른가

  • 삽입/검색: 문자열 길이 \(L\)에 비례해 \(O(L)\). 집합의 크기와 무관합니다.
  • 접두사 질의: "이 접두사로 시작하는 단어가 있는가/몇 개인가"를 \(O(L)\)에.

해시셋도 단어 존재는 빠르지만, 접두사 관련 질의(자동완성, 접두사 개수)는
트라이가 자연스럽습니다.

언제 쓰나

  • 사전에 단어 삽입·검색·접두사 카운트가 필요할 때.
  • 여러 문자열의 공통 접두사 구조가 중요할 때.
  • 비트를 문자처럼 보는 이진 트라이로 XOR 최대/최소 질의를 풀 때.
  • 여러 패턴 동시 검색(아호–코라식)의 토대로.

노드 구조

각 노드는 다음을 가집니다.

  • 자식 링크: 다음 글자 → 자식 노드. 알파벳이 작고 고정이면 배열
    child[26], 크거나 유니코드면 map/해시.
  • 종료 플래그 isEnd: 이 노드에서 끝나는 단어가 있는가.
  • (선택) 카운트: 이 노드를 지나는 단어 수(접두사 개수), 끝나는 단어 수 등.

작은 예제

{"to", "tea", "ted", "ten", "A"} 를 넣으면 루트의 자식은 t 와 A.
t → e 아래 a, d, n 세 갈래가 갈립니다. "te" 로 시작하는 단어는
\(3\)개(tea,ted,ten)이고, 각 노드에 "지나간 단어 수"를 세어 두면 이 값을
\(O(L)\)에 답할 수 있습니다.

복잡도

  • 단어 삽입/검색: \(O(L)\), 알파벳 배열 방식이면 상수도 작음.
  • 공간: 최악 \(O(\sum L_i \times \sigma)\) (\(\sigma\) = 알파벳 크기). 배열 노드는
    빠르지만 메모리를 많이 쓰고, map 노드는 메모리 절약이지만 상수가 큽니다.

정리

  • 트라이는 공통 접두사를 공유하는 글자 단위 트리.
  • 삽입·검색·접두사 질의가 모두 문자열 길이 \(O(L)\).
  • 노드 = 자식 링크 + 종료 플래그 (+ 카운트).

다음 강의에서 배열·맵·정적 풀 기반 구현을 봅니다.

Lesson 트라이 구현 — 배열·맵·정적 풀 선택 8m

배열 기반 트라이 (C++, 소문자 26)

가장 빠른 형태. 노드를 벡터에 담아 인덱스로 참조합니다(포인터·new 없이
정적 풀 방식이라 메모리 관리가 안전하고 빠릅니다).

#include <bits/stdc++.h>
using namespace std;

struct Trie {
    struct Node {
        int child[26];
        int cntEnd = 0;    // 이 노드에서 끝나는 단어 수
        int cntPass = 0;   // 이 노드를 지나는 단어 수(접두사 카운트)
        Node() { memset(child, -1, sizeof(child)); }
    };
    vector<Node> t;
    Trie() { t.emplace_back(); }        // 0번 = 루트

    void insert(const string& s) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[cur].child[c] == -1) {
                t[cur].child[c] = t.size();
                t.emplace_back();
            }
            cur = t[cur].child[c];
            t[cur].cntPass++;
        }
        t[cur].cntEnd++;
    }

    bool search(const string& s) {      // 단어로서 존재?
        int cur = walk(s);
        return cur != -1 && t[cur].cntEnd > 0;
    }
    int countPrefix(const string& s) {  // 이 접두사로 시작하는 단어 수
        int cur = walk(s);
        return cur == -1 ? 0 : t[cur].cntPass;
    }
private:
    int walk(const string& s) {         // s 끝 노드 인덱스, 없으면 -1
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[cur].child[c] == -1) return -1;
            cur = t[cur].child[c];
        }
        return cur;
    }
};

insert 중 t.emplace_back() 이 벡터를 재할당하면 참조가 무효화될 수 있으니
인덱스로 접근(t[cur])하는 것이 안전합니다. 포인터를 캐싱해 두면 위험합니다.

맵 기반 트라이 (알파벳이 크거나 유니코드)

struct Node {
    unordered_map<char, int> nxt;
    int cntEnd = 0, cntPass = 0;
};
vector<Node> t(1);   // 루트

void insert(const string& s) {
    int cur = 0;
    for (char ch : s) {
        auto it = t[cur].nxt.find(ch);
        int nx;
        if (it == t[cur].nxt.end()) {
            nx = t.size(); t.push_back({});
            t[cur].nxt[ch] = nx;
        } else nx = it->second;
        cur = nx; t[cur].cntPass++;
    }
    t[cur].cntEnd++;
}

메모리는 절약되지만 해시 상수 때문에 배열판보다 느립니다.

파이썬 구현 (딕셔너리)

class Trie:
    def __init__(self):
        self.root = {}          # 각 노드는 dict: 글자 -> 자식노드
    def insert(self, s):
        cur = self.root
        for ch in s:
            cur = cur.setdefault(ch, {})
            cur["#pass"] = cur.get("#pass", 0) + 1
        cur["#end"] = cur.get("#end", 0) + 1
    def search(self, s):
        cur = self.root
        for ch in s:
            if ch not in cur:
                return False
            cur = cur[ch]
        return cur.get("#end", 0) > 0

파이썬은 딕셔너리 중첩이 가장 간단합니다(카운트 키는 '#' 접두로 충돌 회피).

정리

  • 배열 노드는 빠르고, 맵 노드는 메모리를 아낀다.
  • 정적 풀(벡터+인덱스) 방식이 포인터 방식보다 안전·빠르다.
  • cntEnd(끝나는 단어 수)와 cntPass(지나는 단어 수)를 두면 존재·접두사
    카운트를 모두 \(O(L)\)에 답한다.
Lesson 심화·변형 — 접두사 질의, 이진 트라이, 메모리 선택 8m

접두사 질의와 메모리 전략

트라이의 진짜 힘은 접두사 관련 질의입니다. 자동완성 후보 수, 공통 접두사 길이,
접두사 그룹 통계 등이 노드의 카운트로 즉시 나옵니다.

  • cntPass 로 "접두사로 시작하는 단어 수".
  • 각 노드에서 자식 링크 존재로 "다음에 올 수 있는 글자".
  • 삭제가 필요하면 insert 의 역과정으로 경로의 cntPass, cntEnd 를 감소.

흔한 함정

  • 메모리 폭발: 배열 노드 child[26] 는 단어가 많으면 \(O(\text{노드수}\times 26)\).
    알파벳이 크면(\(\sigma \ge 26\)) 반드시 맵/정적 풀을 고려하세요.
  • 벡터 재할당 무효화: emplace_back 뒤 이전 Node& 참조가 깨질 수 있음 →
    인덱스로 접근.
  • 종료 vs 경유 혼동: "단어 존재"는 cntEnd, "접두사 존재"는 경로가
    존재하는지로 판단. 둘을 섞으면 접두사만 있는 문자열을 단어로 오인.
  • 대소문자·문자 범위: ch - 'a' 는 소문자 가정. 대문자·숫자·기호가 섞이면
    인덱스 매핑을 넓히거나 맵을 쓰세요.

변형 1: 이진 트라이와 XOR 최대

수를 상위 비트부터 \(30\)비트 문자열처럼 보고 트라이에 넣으면, 주어진 \(x\)와
XOR이 최대가 되는 값을 각 비트에서 "반대 비트 자식"으로 탐욕적으로 내려가며
\(O(30)\)에 찾습니다.

struct BinTrie {
    vector<array<int,2>> ch{{{-1,-1}}};
    void insert(int x) {
        int cur = 0;
        for (int b = 29; b >= 0; b--) {
            int d = (x >> b) & 1;
            if (ch[cur][d] == -1) { ch[cur][d] = ch.size(); ch.push_back({-1,-1}); }
            cur = ch[cur][d];
        }
    }
    int maxXor(int x) {                 // 삽입된 값 중 x와 XOR 최대
        int cur = 0, res = 0;
        for (int b = 29; b >= 0; b--) {
            int d = (x >> b) & 1;
            if (ch[cur][d ^ 1] != -1) { res |= (1 << b); cur = ch[cur][d ^ 1]; }
            else cur = ch[cur][d];
        }
        return res;
    }
};

변형 2: 최장 공통 접두사(그룹)

여러 단어를 넣고 어떤 노드에서 처음으로 갈래가 갈리는 지점까지가 전체의
공통 접두사입니다. 트리를 DFS하며 자식이 둘 이상 되거나 종료가 나오는 지점에서
멈춥니다.

변형 3: 아호–코라식의 토대

트라이에 여러 패턴을 넣고 실패 링크(접미사 링크) 를 추가하면 텍스트를 한 번
훑어 모든 패턴의 모든 출현을 찾는 아호–코라식 이 됩니다(다음 단원). 트라이의
노드·자식 구조를 그대로 재사용하므로, 여기서 트라이를 확실히 익혀 두면 이후가
수월합니다.

정리

  • 접두사 카운트·자동완성은 노드 카운트로 즉시.
  • 메모리 전략(배열 vs 맵 vs 정적 풀)을 알파벳 크기·단어 수로 판단.
  • 이진 트라이(XOR), 공통 접두사, 아호–코라식으로 자연스럽게 확장된다.
Practice problem 최대 보안 강도 선택 25m
R00254

최대 보안 강도

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 사전 검색 선택 25m
R00253

사전 검색

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
04
Level 5 · Analyst

Analyst

문자열 알고리즘 · Analyst 단계

0/13 완료
Lesson 실패 함수와 선형 문자열 검색 필수 8m

어떤 문제를 푸는가

길이 \(N\)인 텍스트 \(T\) 안에서 길이 \(M\)인 패턴 \(P\)가 등장하는 모든 위치를
찾습니다. 단순 비교는 각 시작 위치마다 패턴을 처음부터 맞춰 보아 최악
\(O(NM)\)입니다. KMP(Knuth–Morris–Pratt) 는 이를 \(O(N + M)\)으로 줄입니다.

단순 검색의 낭비

T = "aaaaab", P = "aaab" 를 단순 비교하면, 한 위치에서 aaa 까지 맞다가
b 에서 어긋날 때 텍스트 포인터를 한 칸만 뒤로 물려 처음부터 다시 봅니다.
그러나 우리는 이미 aaa 가 맞았다는 정보를 알고 있습니다.
이 정보를 버리지 않는 것 이 KMP의 핵심입니다.

실패 함수 (failure / \(\pi\) 배열)

패턴 자신에 대해, 각 접두사에서 "진부분 접두사이면서 동시에 접미사인 가장 긴
문자열의 길이"를 미리 계산합니다. 이를 \(\pi[i]\)라 합니다.

$$ \pi[i] = P[0..i]\ \text{의 접두사이자 접미사인 가장 긴 진부분 문자열 길이} $$

예: \(P = \) "ababa" 면 \(\pi = [0, 0, 1, 2, 3]\).
"abab" 의 접두=접미는 "ab"(길이 2), "ababa" 는 "aba"(길이 3)입니다.

이 값이 있으면, 매칭 중 어긋났을 때 "패턴의 어디로 점프해 다시 비교할지"를
즉시 알 수 있고, 텍스트 포인터는 절대 뒤로 가지 않습니다.

매칭 과정 직관

텍스트를 왼쪽에서 오른쪽으로 한 번 훑습니다. 현재 패턴의 \(j\)개 글자가 맞아 있는
상태에서 다음 글자가 어긋나면, \(j\)를 \(\pi[j-1]\)로 줄여 "이미 일치하는 접두사"를
재활용해 다시 시도합니다. \(j\)가 \(M\)에 도달하면 한 번의 출현입니다.

왜 선형인가

텍스트 포인터 \(i\)는 매 글자마다 한 번만 전진하므로 \(O(N)\)입니다. 패턴 포인터
\(j\)는 어긋날 때 줄지만, 늘어난 총량(맞을 때 \(+1\))을 넘게 줄 수 없으므로 \(j\)의
총 변화량도 \(O(N)\)입니다. 실패 함수 계산도 같은 논리로 \(O(M)\). 전체

$$ O(N + M). $$

핵심 직관

실패 함수는 패턴 내부의 자기 닮음(반복 구조) 을 미리 요약한 표입니다. 이 표
덕분에 어긋남이 생겨도 처음부터 다시 보지 않고 이미 확보한 일치를 재활용합니다.
다음 강의에서 실패 함수와 검색의 구현을, 그리고 형제 도구인 Z 함수를 봅니다.

Lesson KMP 구현과 Z 함수 선택 8m

실패 함수 계산 (C++)

패턴과 텍스트 검색이 같은 모양이라는 점이 KMP의 우아함입니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> getPi(const string& p) {
    int m = p.size();
    vector<int> pi(m, 0);
    int j = 0;                       // 현재 일치한 접두사 길이
    for (int i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];           // 어긋나면 더 짧은 접두=접미로 후퇴
        if (p[i] == p[j]) j++;
        pi[i] = j;
    }
    return pi;
}

텍스트에서 패턴 찾기 (C++)

vector<int> kmp(const string& t, const string& p) {
    vector<int> pi = getPi(p), res;
    int n = t.size(), m = p.size(), j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && t[i] != p[j])
            j = pi[j - 1];
        if (t[i] == p[j]) j++;
        if (j == m) {                    // 패턴 한 번 완성
            res.push_back(i - m + 1);    // 0-based 시작 위치
            j = pi[j - 1];               // 겹치는 다음 출현을 위해 후퇴
        }
    }
    return res;                          // 모든 출현 시작 위치
}

매칭 루프가 실패 함수 계산과 거의 같음을 보세요. j = pi[j-1] 로의 후퇴가
두 경우 모두 핵심입니다.

파이썬 구현

def get_pi(p):
    m = len(p)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
        pi[i] = j
    return pi

def kmp(t, p):
    pi = get_pi(p)
    res, j = [], 0
    for i, c in enumerate(t):
        while j > 0 and c != p[j]:
            j = pi[j - 1]
        if c == p[j]:
            j += 1
        if j == len(p):
            res.append(i - len(p) + 1)
            j = pi[j - 1]
    return res

형제 도구: Z 함수

Z 함수 \(z[i]\)는 "문자열 \(s\)와 \(s[i..]\)가 앞에서부터 몇 글자나 같은가"입니다
(\(z[0]\)은 보통 정의하지 않거나 \(0\)/\(n\)으로 둠). \([l, r]\) 구간(가장 오른쪽까지
뻗은 일치 구간)을 유지하며 \(O(n)\)에 계산합니다.

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);   // 이미 아는 구간 재활용
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

패턴 검색은 P + '#' + T 의 Z 함수에서 \(z[i] = M\) 인 위치를 찾으면 됩니다.
'#' 는 \(P\)·\(T\) 어디에도 없는 구분자여야 합니다. KMP의 \(\pi\)와 Z는 서로
변환 가능하며, 문제에 따라 편한 쪽을 씁니다.

정리

  • \(\pi\) 계산과 매칭은 같은 골격(while 후퇴 + 조건부 전진).
  • 출현 후 j = pi[j-1] 로 후퇴해야 겹치는 출현을 놓치지 않는다.
  • Z 함수는 \(\pi\)의 형제 도구로, P#T 패턴 검색과 여러 문자열 성질 계산에 쓰인다.
Lesson 심화·변형 — 주기·경계·회전, 해시 비교 선택 8m

흔한 함정

  • while vs if: 어긋남 처리는 반드시 while 입니다. 한 번의 후퇴로
    안 맞을 수 있어 여러 단계 후퇴가 필요합니다. if 로 쓰면 조용히 틀립니다.
  • 출현 후 후퇴 누락: j == m 직후 j = pi[j-1] 을 빼면 겹치는 다음
    출현을 놓치거나 인덱스가 꼬입니다.
  • 인덱스 0/1 기준: 출력 형식(0-based / 1-based)을 문제에 맞추세요.
    위 구현은 0-based 시작 위치를 반환합니다.
  • 빈 패턴/M > N: 경계 확인. \(M = 0\) 이면 모든 위치가 출현으로 볼지
    정의에 따릅니다.
  • Z 함수 구분자: P#T 에서 # 가 입력에 등장하면 오답. 입력 알파벳에
    없는 문자를 골라야 합니다.

변형 1: 최소 주기(period)

길이 \(n\) 문자열에서 \(k = \pi[n-1]\) 일 때, 후보 주기는 \(n - k\) 입니다.

$$ n \bmod (n-k) = 0 \ \Rightarrow\ \text{길이 } (n-k)\ \text{패턴의 반복} $$

이때 반복 횟수는 \(n / (n-k)\). "abcabcabc" 는 \(\pi[8]=6\), 주기 \(3\),
세 번 반복입니다. 조건이 성립하지 않으면 그 문자열은 온전한 반복이 아닙니다.

변형 2: 모든 경계(border)

접두사이자 접미사인 모든 길이는 \(\pi[n-1]\) 에서 시작해 \(\pi\) 체인을 타고
내려가며 수집합니다.

vector<int> allBorders(const string& s) {
    vector<int> pi = getPi(s), res;
    int k = pi[(int)s.size() - 1];
    while (k > 0) { res.push_back(k); k = pi[k - 1]; }
    return res;   // 길이 내림차순
}

변형 3: 출현 횟수 / 각 접두사의 등장 수

\(\pi\) 배열로 "각 접두사가 문자열 전체에서 몇 번 등장하는가"를 셀 수 있습니다.
\(cnt[i]\)를 접두사 길이 \(i\)의 등장 횟수라 하면, 먼저 각 \(\pi\)값에 \(1\)을 세고
길이 내림차순으로 \(cnt[\pi[i-1]] \mathrel{+}= cnt[i]\) 를 누적합니다.

vector<int> prefixCount(const string& s) {
    int n = s.size();
    vector<int> pi = getPi(s), cnt(n + 1, 0);
    for (int i = 0; i < n; i++) cnt[pi[i]]++;
    for (int i = n - 1; i > 0; i--) cnt[pi[i - 1]] += cnt[i];
    for (int i = 0; i <= n; i++) cnt[i]++;   // 접두사 자기 자신 포함
    return cnt;   // cnt[len] = 길이 len 접두사의 등장 횟수
}

변형 4: 회전·부분 문자열 판정

  • \(B\)가 \(A\)의 회전인지: \(A\)와 \(B\)의 길이가 같고 \(B\)가 \(A + A\)의 부분
    문자열이면 회전입니다(kmp(A+A, B) 에 출현이 있는지).
  • 부분 문자열 포함 판정도 kmp 결과가 비어 있지 않은지로 확인합니다.

변형 5: 해시와의 관계, 안티-해시 주의

문자열 검색은 다항식 해싱(롤링 해시)으로도 \(O(N)\) 기대 시간에 됩니다. 다만
단일 모듈러 해시는 저격(anti-hash) 입력에 충돌당할 수 있으므로, 서로 다른 큰
소수 두 개로 더블 모듈러(두 해시를 쌍으로 비교)를 쓰고, 밑(base)을 난수로
고르는 것이 안전합니다. KMP는 이런 충돌 위험이 없는 결정적 \(O(N+M)\)이라,
정확성이 중요하면 KMP가 더 안전한 선택입니다.

정리

  • while 후퇴, 출현 후 후퇴, 인덱스 기준을 항상 확인.
  • \(\pi\) 하나로 주기·경계·접두사 등장 횟수·회전 판정까지 파생된다.
  • 해시는 편하지만 안티-해시 위험이 있어 더블 모듈러가 필요; KMP는 결정적.
Practice problem 알파카컵 1회: F - 알파카의 끝없는 울음소리 선택 25m
A00006

알파카컵 1회: F - 알파카의 끝없는 울음소리

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 문자열의 최소 주기 선택 25m
R00366

문자열의 최소 주기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Lesson Z 배열과 $O(N)$ 매칭 — 개념 필수 8m

어떤 문제를 푸는가

Z 알고리즘 은 문자열 \(s\) 에 대해 Z 배열 을 \(O(N)\) 에 계산합니다. \(Z[i]\) 는 "\(s\) 와 \(s\) 의 \(i\) 번째 접미사 가 앞에서부터 몇 글자나 일치하는가", 즉 \(s\) 와 \(s[i\,{:}\,]\) 의 최장 공통 접두사 길이 입니다.

$$ Z[i] = \max\{\,k : s[0\,{:}\,k] = s[i\,{:}\,i+k]\,\}, \qquad Z[0] = |s|\ (\text{관례}) $$

이 하나의 배열로 문자열 매칭, 주기, 서로 다른 부분문자열 등을 선형에 처리합니다.

1. 예시

\(s = \texttt{aabxaabxcaabxaabxay}\) 에서 \(Z[4] = 4\) 입니다(\(\texttt{aabx}\) 가 다시 등장). 이런 "여기서부터 앞부분(접두사)이 얼마나 반복되나" 를 모든 위치에서 한 번에 구하는 것이 Z 배열입니다.

2. 핵심 — Z 박스(구간 재사용)

지금까지 계산하며 만난 가장 오른쪽까지 뻗은 일치 구간 \([l, r]\) 을 유지합니다(\(s[l\,{:}\,r+1] = s[0\,{:}\,r-l+1]\)). 새 위치 \(i\) 를 계산할 때:

  • \(i \le r\) 이면 \(i\) 는 이미 아는 구간 안에 있으므로, 대칭 위치 \(i - l\) 의 값을 재사용합니다: \(Z[i] \ge \min(r - i + 1,\ Z[i - l])\).
  • 그 뒤 경계에서만 한 글자씩 확장 하고, \(i + Z[i] - 1 > r\) 이면 \([l, r]\) 을 갱신합니다.

$$ Z[i] \leftarrow \min(r - i + 1,\; Z[i-l]),\quad \text{그 후 } s[Z[i]] = s[i+Z[i]] \text{인 동안 }++ $$

각 글자는 "확장" 으로 최대 한 번만 비교되므로 전체가 \(O(N)\) 입니다.

3. 문자열 매칭에 쓰기

패턴 \(p\) 를 텍스트 \(t\) 에서 찾으려면, 둘 사이에 어디에도 안 나오는 구분자 # 를 끼워

$$ S = p + \texttt{\#} + t $$

의 Z 배열을 구합니다. 위치 \(i\)(\(t\) 영역)에서 \(Z[i] \ge |p|\) 이면 그 자리에서 \(p\) 가 정확히 등장합니다.

$$ p \text{ 가 } t[j\,{:}\,]\text{에서 시작} \iff Z[\,|p| + 1 + j\,] \ge |p| $$

4. 복잡도 · KMP와의 관계

  • Z 배열: 시간 \(O(N)\), 공간 \(O(N)\). 매칭도 \(O(|p| + |t|)\).
  • KMP의 실패 함수와 정보량이 동등 합니다(서로 변환 가능). Z는 "접두사와의 일치 길이" 를 직접 주어 직관적이고, KMP는 온라인(스트리밍) 처리에 강합니다.

5. 언제 쓰나

  • 패턴 매칭, 주기/테두리(경계) 판정, 서로 다른 부분문자열 세기, 문자열 압축 판정.
  • "여기서부터 앞부분이 얼마나 반복되나" 가 필요한 모든 곳.

다음 강의에서 검증된 구현과 KMP 대조를 봅니다.

Lesson 구현 — Z 함수와 매칭 선택 8m

구현 — Z 함수

1. C++ (표준, \(O(N)\))

#include <bits/stdc++.h>
using namespace std;
vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = n;                              // 관례: 자기 자신
    int l = 0, r = 0;                      // 가장 오른쪽까지 뻗은 일치 구간
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);   // 박스 내부: 재사용
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;  // 확장
        if (i + z[i] > r) { l = i; r = i + z[i]; }             // 박스 갱신
    }
    return z;
}

i < r 에서 min(r - i, ...) 는 구간 끝을 넘지 않게 자르는 것입니다(관례상 \(r\) 을 "끝+1" 로 둔 형태). 위 코드는 브루트포스와 2만 케이스 대조로 검증됨.

2. 매칭 — \(p + \texttt{\#} + t\)

// t에서 p가 시작하는 모든 위치(0-index) 반환
vector<int> find_all(const string& t, const string& p) {
    string s = p + '\x01' + t;             // '\x01': 입력에 없는 구분자
    vector<int> z = z_function(s), res;
    int m = p.size();
    for (int i = m + 1; i < (int)s.size(); i++)
        if (z[i] >= m) res.push_back(i - m - 1);
    return res;
}

3. Python

def z_function(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

def find_all(t, p):
    s = p + '\x01' + t
    z = z_function(s)
    m = len(p)
    return [i - m - 1 for i in range(m + 1, len(s)) if z[i] >= m]

4. 변형 — 서로 다른 부분문자열 개수

각 접미사를 앞에서부터 추가하며, 새 접미사가 기존 접두사들과 겹치는 최대 길이를 Z로 구하면 새로 생기는 부분문자열 수 를 누적할 수 있습니다(접미사 자동자/배열의 간이 대체).

5. 변형 — 주기 판정

문자열 \(s\)(\(|s| = n\))가 길이 \(p\) 의 반복으로 이뤄지려면

$$ Z[p] = n - p \ \text{이고}\ n \bmod p = 0 $$

이면 \(s\) 는 주기 \(p\) 를 가집니다. Z 배열 하나로 최소 주기·경계를 즉시 판정할 수 있습니다.

Lesson 심화·변형 — KMP 비교, 주기·경계, 함정 선택 8m

심화·변형 — Z의 응용과 주의

1. Z ↔ KMP 실패 함수 (동등성)

두 배열은 같은 정보를 다르게 담습니다.

  • \(Z[i]\): \(s\) 와 \(s[i{:}]\) 의 최장 공통 접두사 길이(전방).
  • \(\pi[i]\)(KMP 실패 함수): \(s[0{:}i+1]\) 의 최장 경계(접두사=접미사) 길이(후방).

서로 변환 가능하며, \(\pi\) 로부터 \(Z\) 를, \(Z\) 로부터 \(\pi\) 를 \(O(N)\) 에 얻습니다. 선택 기준:

Z KMP
직관 "접두사 반복" 직접 실패 함수
온라인(스트리밍) 어려움 쉬움
구현 길이 짧음 짧음
경계·주기 둘 다 가능 둘 다 가능

매칭 한 번이면 취향 차이, 스트리밍/자동자 가 필요하면 KMP가 유리합니다.

2. 구분자 함정

매칭용 \(p + \texttt{sep} + t\) 에서 \(\texttt{sep}\) 는 \(p\) 와 \(t\) 어디에도 없는 문자 여야 합니다. 소문자만 온다면 # 로 충분하지만, 임의 바이트가 오면 '\x01' 처럼 확실히 없는 값을 쓰세요. 구분자가 실제 문자와 겹치면 \(Z[i] \ge m\) 이 경계를 넘어 오검출 됩니다.

3. \(r\) 관례 통일

Z 구현에는 \(r\) 을 "구간의 끝 인덱스" 로 두는 판과 "끝+1" 로 두는 판이 섞여 있습니다. 한 관례로 통일하세요. 위 강의 코드는 갱신 시 r = i + z[i](끝+1)로 두고 i < r, min(r - i, ...) 로 맞춘 형태입니다. 섞으면 off-by-one으로 틀립니다.

4. 주기·경계 정리

  • 최소 주기: 가장 작은 \(p\) 로 \(Z[p] = n - p,\ n \bmod p = 0\). 없으면 주기는 \(n\)(주기적 아님).
  • 모든 경계(테두리): \(Z[i] = n - i\) 인 \(i\) 들이 곧 접두사=접미사 길이 \(n-i\) 의 경계에 대응.
  • 회전/최소 표현: \(s+s\) 에 Z를 걸어 특정 회전이 원본과 일치하는지 판정.

5. 자주 하는 실수

  • z[0] 을 0으로 둠 — 관례상 \(|s|\)(또는 매칭 로직이 \(i \ge 1\) 만 보게 함). 응용마다 규약을 명확히.
  • 확장 while 의 범위 검사 누락: i + z[i] < n 을 빠뜨리면 범위 밖 접근.
  • 매칭에서 인덱스 환산 실수: 위치 \(= i - |p| - 1\).
  • 큰 알파벳/유니코드: 파이썬은 문자 단위라 안전, C++은 string(바이트) 기준임을 유의.

6. 요약

Z 배열은 "모든 위치에서 접두사와의 일치 길이" 를 \(O(N)\) 에 주는 만능 도구입니다. 매칭·주기·경계·회전이 전부 이 한 배열의 질의로 환원되며, KMP와는 정보 동등—직관은 Z, 스트리밍은 KMP 로 기억하세요.

Practice problem Longest Prefix Match Inside a String 선택 25m
R03302

Longest Prefix Match Inside a String

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Lesson 중심 확장과 팰린드롬 반지름 $O(N)$ — 개념 필수 8m

어떤 문제를 푸는가

매내처(Manacher) 알고리즘 은 문자열의 모든 중심에 대한 팰린드롬 반지름 을 \(O(N)\) 에 구합니다. 이걸로 "최장 팰린드롬 부분문자열", "팰린드롬 개수" 등을 선형에 해결합니다.

각 위치를 중심으로 양옆으로 뻗을 수 있는 최대 팰린드롬 길이를 모두 아는 것이 목표입니다. 순진하게 모든 중심에서 확장하면 \(O(N^2)\) — 매내처는 이미 계산한 큰 팰린드롬 안의 대칭성 을 재사용해 \(O(N)\) 으로 줄입니다.

1. 홀·짝 통합 변환

팰린드롬은 길이가 홀수(중심 1글자)일 수도 짝수(중심 두 글자 사이)일 수도 있어 성가십니다. 글자 사이마다 구분자 # 를 삽입 하면 모든 팰린드롬이 홀수 길이 로 통일됩니다.

$$ \texttt{abba} \;\to\; \texttt{\#a\#b\#b\#a\#} $$

변환 문자열 \(t\) 의 위치 \(i\) 에서의 반지름 \(p[i]\) 를 구하면, 원문의 팰린드롬 길이는 정확히 \(p[i]\) 가 됩니다(구분자 덕에 홀·짝이 자동 처리).

2. 핵심 — 거울 대칭 재사용

지금까지 가장 오른쪽까지 뻗은 팰린드롬의 중심 \(c\) 와 오른쪽 끝 \(r\) 을 유지합니다. 새 위치 \(i \le r\) 이면, \(c\) 기준 대칭 위치 \(mir = 2c - i\) 의 값을 재사용합니다.

$$ p[i] \leftarrow \min\bigl(r - i,\; p[\,2c - i\,]\bigr) $$

그 뒤 경계에서만 한 글자씩 확장 하고, \(i + p[i] > r\) 이면 \((c, r)\) 을 갱신합니다. 각 글자는 확장으로 최대 한 번 비교되어 전체 \(O(N)\).

3. 최장 팰린드롬 복원

모든 \(p[i]\) 중 최댓값이 최장 팰린드롬 길이입니다. 원문에서의 시작 위치는 변환 좌표에서 역산합니다:

$$ \text{len} = \max_i p[i], \qquad \text{start} = \frac{(i - p[i])}{2}\ (\text{변환 좌표 } i \text{ 기준}) $$

4. 팰린드롬 개수

위치 \(i\) 가 (변환 문자열에서) 반지름 \(p[i]\) 를 가지면, 그 중심에서 만들어지는 서로 다른 팰린드롬 부분문자열 수 는 \(\lceil p[i]/2 \rceil\) 개입니다. 모두 더하면 전체 팰린드롬 부분문자열의 총 개수를 \(O(N)\) 에 얻습니다.

5. 복잡도 · 언제 쓰나

  • 시간 \(O(N)\), 공간 \(O(N)\). 중심 확장 브루트포스 \(O(N^2)\) 대비 결정적 우위.
  • "최장/개수/특정 길이 팰린드롬" 을 큰 \(N\) 에서 물을 때.

다음 강의에서 검증된 구현(변환·반지름·복원)을 봅니다.

Lesson 구현 — 변환·반지름·복원 선택 8m

구현 — 매내처

1. C++ (경계 보초 포함, \(O(N)\))

양 끝에 서로 다른 보초 ^, $ 를 두면 경계 검사를 생략할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
// p[i] = 변환 문자열 t에서 중심 i의 팰린드롬 반지름
vector<int> manacher(const string& s) {
    string t = "^";
    for (char c : s) { t += '#'; t += c; }
    t += "#$";                              // 양 끝 보초 (서로, 본문과 다름)
    int n = t.size();
    vector<int> p(n, 0);
    int c = 0, r = 0;
    for (int i = 1; i < n - 1; i++) {
        if (i < r) p[i] = min(r - i, p[2 * c - i]);   // 거울 재사용
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;  // 확장(보초가 멈춤)
        if (i + p[i] > r) { c = i; r = i + p[i]; }
    }
    return p;
}
// 최장 팰린드롬 부분문자열
string longest_pal(const string& s) {
    vector<int> p = manacher(s);
    int best = 0, center = 0;
    for (int i = 0; i < (int)p.size(); i++)
        if (p[i] > best) { best = p[i]; center = i; }
    int start = (center - best) / 2;        // 원문 좌표로 환산
    return s.substr(start, best);
}

위 manacher/longest_pal 은 브루트포스와 5만 케이스 대조로 검증됨.

2. Python

def manacher(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    c = r = 0
    for i in range(n):
        if i < r:
            p[i] = min(r - i, p[2 * c - i])
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and \
              t[i - p[i] - 1] == t[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    return p                                 # p[i] == 원문 팰린드롬 길이

def longest_pal(s):
    p = manacher(s)
    best = max(range(len(p)), key=lambda i: p[i])
    length = p[best]
    start = (best - length) // 2
    return s[start:start + length]

3. 변형 — 팰린드롬 개수 세기

long long count_palindromes(const string& s) {
    vector<int> p = manacher(s);
    long long total = 0;
    for (int x : p) total += (x + 1) / 2;   // 각 중심의 팰린드롬 수
    return total;
}

4. 좌표 환산 요약

변환 문자열 좌표 \(i\), 반지름 \(p[i]\) 에 대해 원문에서:

$$ \text{길이} = p[i], \qquad \text{시작} = \frac{i - p[i]}{2} $$

보초 ^ … $ 를 쓰면 확장 루프에서 범위 검사를 생략 할 수 있어 코드가 짧고 빠릅니다(파이썬 판은 명시적 범위 검사를 사용).

Lesson 심화·변형 — 함정, 좌표, 응용 선택 8m

심화·변형 — 주의와 확장

1. 가장 흔한 함정 — 좌표 환산

변환 문자열 \(t = \texttt{\#a\#b\#\dots}\) 의 좌표와 원문 좌표를 혼동하면 복원이 틀립니다. 규칙을 고정하세요:

  • 보초 ^ 를 앞에 둔 구현: 원문 시작 \(= (i - p[i]) / 2\).
  • 보초 없이 #a#b# 만 쓴 구현: 원문 시작 \(= (i - p[i]) // 2\).

두 경우 offset이 다르니 자기 구현 한 가지에 맞춰 소규모로 검증하고 고정하세요.

2. 반지름의 의미 통일

구현마다 \(p[i]\) 가 "포함 반지름" 인지 "확장 횟수" 인지 다릅니다. 위 강의 구현은 변환 문자열에서의 반지름이 곧 원문 팰린드롬 길이 가 되도록 # 삽입을 설계했습니다. 이 불변식(\(p[i] = \) 원문 길이)을 기억하면 개수·복원 공식이 일관됩니다.

3. 보초 vs 명시적 범위 검사

  • 보초(^, $): 확장 while 이 서로 다른 경계 문자에서 자동으로 멈춰 범위 검사 불필요 — C++에서 빠르고 깔끔.
  • 명시적 검사: i - p[i] - 1 >= 0 && i + p[i] + 1 < n — 파이썬 등에서 안전.

보초를 쓸 땐 보초 문자가 본문·구분자와 모두 달라야 합니다(^, #, $ 서로 다름).

4. 거울 재사용의 정확성

\(p[i] \leftarrow \min(r - i,\ p[2c - i])\) 에서 \(\min\) 을 빼먹으면 오른쪽 경계 \(r\) 을 넘는 값을 그대로 믿어 틀립니다. 대칭 위치의 팰린드롬이 현재 큰 팰린드롬 밖으로 삐져나온 경우, 경계까지만 보장되고 그 너머는 직접 확장으로 확인 해야 하기 때문입니다.

5. 응용

문제 방법
최장 팰린드롬 부분문자열 \(\max p[i]\) + 복원
팰린드롬 부분문자열 개수 \(\sum \lceil p[i]/2 \rceil\)
각 위치에서 끝나는/시작하는 팰린드롬 수 \(p\) 로 구간 누적
특정 길이 팰린드롬 존재 \(p[i] \ge L\) 인 중심 탐색
회문 분할·팩토라이제이션 \(p\) 로 팰린드롬 판정 후 DP

더 복잡한 팰린드롬 구조(모든 서로 다른 팰린드롬 열거, 팰린드롬 트리)는 회문 트리(Eertree) 로 확장됩니다.

6. 자주 하는 실수 체크

  • 홀·짝 통합용 # 삽입 누락 → 짝수 팰린드롬 놓침.
  • \(\min(r - i, \dots)\) 누락 → 경계 초과 오검출.
  • 좌표 환산 offset 혼동 → 복원 위치 어긋남.
  • 개수 공식 \((p+1)/2\) 대신 \(p\) 를 그냥 더함 → 중복/과다 계산.

매내처의 본질은 "큰 팰린드롬의 대칭성으로 안쪽 계산을 공짜로 얻고, 경계만 확장" 하여 \(O(N)\) 을 달성하는 것입니다.

Practice problem 가장 긴 회문 부분문자열 길이 선택 25m
R01520

가장 긴 회문 부분문자열 길이

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
05
Level 6 · Strategist

Strategist

문자열 알고리즘 · Strategist 단계

0/9 완료
Lesson 접미사 정렬과 LCP·Kasai의 원리 필수 8m

접미사 배열이란

문자열 \(S\)(길이 \(n\))의 접미사 배열(suffix array) \(SA\)는, 모든 접미사
\(S[i..n-1]\)를 사전순으로 정렬했을 때의 시작 인덱스 목록입니다. 즉 \(SA[k]\)는
사전순으로 \(k\)번째로 작은 접미사의 시작 위치입니다.

접미사 트리보다 메모리가 적고 구현이 간단해, 부분 문자열·반복·정렬 관련 문제의
강력한 도구입니다.

예: "banana"

접미사와 그 정렬 결과(\(\@@RISE_MATH_BLOCK_0@@LCP[k] = \operatorname{lcp}\big(S[SA[k-1]..],\ S[SA[k]..]\big)\quad(k \ge 1)\)$

"banana" 에서 \(SA=[5,3,1,0,4,2]\) 이면
\(LCP = [-,\ 1,\ 3,\ 0,\ 0,\ 2]\) 입니다(예: ana 와 anana 의 공통 접두사
ana 길이 \(3\)).

LCP 배열은 "정렬된 접미사들이 서로 얼마나 닮았는가"를 요약하며, 서로 다른 부분
문자열 개수·최장 반복 부분 문자열 등 수많은 질의의 열쇠입니다.

Kasai 알고리즘: LCP를 \(O(n)\)에

LCP를 정의대로 각 쌍마다 비교하면 \(O(n^2)\)입니다. Kasai 알고리즘은
\(SA\)가 있을 때 LCP를 \(O(n)\)에 계산합니다.

핵심 관찰: 접미사 \(S[i..]\)의 LCP(\(h\))를 구한 뒤, 바로 다음 접미사 \(S[i+1..]\)로
넘어가면 공통 접두사가 최대 \(1\)만 줄어듭니다. 왜냐하면 \(S[i..]\)가 앞
접미사와 \(h\)글자 공유했다면, 그 첫 글자를 뗀 \(S[i+1..]\)는 (대응하는 접미사와)
적어도 \(h-1\)글자를 공유하기 때문입니다. 그래서 \(h\)를 매번 \(0\)부터 세지 않고
직전 값에서 \(1\)만 줄여 이어 쓰므로, \(h\)의 총 증가량이 \(O(n)\)으로 묶여 전체
\(O(n)\)이 됩니다.

언제 쓰나

  • 서로 다른 부분 문자열의 개수, 최장 반복/공통 부분 문자열.
  • 사전순 \(k\)번째 부분 문자열, 부분 문자열 검색(이분 탐색).
  • LCP + 희소 테이블로 임의의 두 접미사 LCP를 \(O(1)\) 질의.

정리

  • \(SA\) = 접미사를 사전순 정렬한 시작 인덱스, 접두사 더블링으로 \(O(n\log n)\).
  • \(LCP[k]\) = 정렬 이웃 접미사의 최장 공통 접두사.
  • Kasai는 \(h\)가 \(1\)씩만 감소한다는 관찰로 LCP를 \(O(n)\)에 구한다.

다음 강의에서 구현을 봅니다.

Lesson 접미사 배열·Kasai 구현 (C++/Python) 선택 8m

접미사 배열 구현 (C++)

아래는 접두사 더블링을 비교 정렬로 구현한 \(O(n \log^2 n)\) 버전입니다.
직관적이고 검증이 쉬워 대회에서 널리 쓰입니다(정렬을 기수 정렬로 바꾸면
\(O(n \log n)\)).

#include <bits/stdc++.h>
using namespace std;

vector<int> suffixArray(const string& s) {
    int n = s.size();
    vector<int> sa(n), rnk(n), tmp(n);
    for (int i = 0; i < n; i++) { sa[i] = i; rnk[i] = (unsigned char)s[i]; }
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int a, int b) {
            if (rnk[a] != rnk[b]) return rnk[a] < rnk[b];
            int ra = (a + k < n) ? rnk[a + k] : -1;
            int rb = (b + k < n) ? rnk[b + k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        rnk = tmp;
        if (rnk[sa[n - 1]] == n - 1) break;   // 모든 순위가 유일 -> 완료
    }
    return sa;
}

\(O(n \log n)\)으로 줄이는 법: 매 단계 sort 대신, 순위 쌍
\((\text{rnk}[i], \text{rnk}[i+k])\)를 두 번의 계수 정렬(뒤 키 먼저, 앞 키
나중)로 기수 정렬하면 단계당 \(O(n)\)이 됩니다. 로직은 같고 정렬만 교체합니다.

Kasai LCP 구현 (C++)

vector<int> kasai(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;   // 역배열
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = sa[rank[i] - 1];               // 정렬상 바로 앞 접미사
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
            lcp[rank[i]] = h;                       // lcp[k] = SA[k-1]과 SA[k]의 LCP
            if (h > 0) h--;                          // 다음엔 최대 1만 감소
        } else {
            h = 0;                                   // 가장 작은 접미사엔 앞이 없음
        }
    }
    return lcp;                                      // lcp[0]은 정의상 0/미사용
}

rank[i] 는 접미사 \(i\)의 정렬 순위, lcp[k] 는 \(SA[k-1]\)과 \(SA[k]\)의 LCP로
정렬 인덱스 기준입니다. h 를 \(0\)부터 세지 않고 이어 쓰는 것이 \(O(n)\)의 열쇠.

파이썬 구현

def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rnk = [ord(c) for c in s]
    k = 1
    while k < n:
        def key(i):
            return (rnk[i], rnk[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if key(sa[i - 1]) < key(sa[i]) else 0)
        rnk = tmp
        if rnk[sa[-1]] == n - 1:
            break
        k <<= 1
    return sa

def kasai(s, sa):
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp = [0] * n
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1
        else:
            h = 0
    return lcp

정리

  • 더블링 SA는 순위를 두 배씩 늘리며 정렬; 비교 정렬 \(O(n\log^2 n)\), 기수
    정렬 \(O(n\log n)\).
  • Kasai는 역배열 rank 를 만들고 h 를 이어 쓰며 \(O(n)\).
  • lcp[k] 가 정렬 인덱스 기준이라는 점을 항상 기억.
Lesson 심화·변형 — 서로 다른 부분 문자열, 최장 반복 선택 8m

흔한 함정

  • LCP 인덱스 기준 혼동: lcp[k] 는 원문 위치가 아니라 정렬 순위
    \(SA[k-1]\)과 \(SA[k]\) 사이 값입니다. 원문 위치로 착각하면 모든 후속 계산이
    틀립니다.
  • off-by-one: lcp[0] 은 앞 접미사가 없어 정의되지 않습니다(보통 \(0\)).
    루프에서 rank[i] > 0 확인.
  • 경계 검사: Kasai의 while 에서 i+h<n && j+h<n 을 빠뜨리면 범위 밖 접근.
  • 더블링 종료 조건: 모든 순위가 유일해지면(rnk[sa[n-1]]==n-1) 즉시 종료.
    안 하면 불필요한 단계가 돌거나, k 오버플로에 주의.
  • 문자 부호: 초기 순위로 s[i] 를 쓸 때 unsigned char 로 캐스팅(음수 방지).
  • **끝 문자(\(\@@RISE_MATH_BLOCK_0@@\#\{\text{distinct substrings}\} = \sum_{k=0}^{n-1} (n - SA[k]) - \sum_{k=1}^{n-1} LCP[k].\)$
long long distinctSubstrings(const string& s) {
    auto sa = suffixArray(s);
    auto lcp = kasai(s, sa);
    int n = s.size();
    long long tot = 0;
    for (int k = 0; k < n; k++) tot += (n - sa[k]);
    for (int k = 1; k < n; k++) tot -= lcp[k];
    return tot;
}

변형 2: 최장 반복 부분 문자열

\(LCP\)의 최댓값 이 곧 "적어도 두 번 등장하는 가장 긴 부분 문자열"의 길이입니다
(그 위치는 해당 \(SA[k]\)). 정렬상 이웃한 두 접미사가 가장 많이 겹치는 지점이기
때문입니다.

변형 3: 두 문자열의 최장 공통 부분 문자열

\(A \# B\) (구분자 \(\#\)는 둘에 없는 문자)로 이어 붙여 SA·LCP를 만든 뒤, 정렬상
서로 다른 원본에서 온 이웃 접미사의 \(LCP\) 최댓값을 취합니다. 각 접미사가
\(A\)에서 왔는지 \(B\)에서 왔는지를 시작 위치로 판별합니다.

변형 4: 부분 문자열 검색 / 사전순 k번째

  • 검색: 패턴 \(P\)가 \(S\)에 있는지는 \(SA\) 위에서 이분 탐색으로 \(O(|P|\log n)\).
  • 사전순 \(k\)번째 서로 다른 부분 문자열: \(SA\)를 순회하며 각 접미사가 새로
    기여하는 개수 \((n-SA[k]-LCP[k])\)를 누적해 \(k\)가 걸리는 접미사·길이를 찾습니다.

변형 5: 임의 두 접미사의 LCP를 \(O(1)\)에

\(LCP\) 배열은 정렬 이웃만 다루지만, 두 접미사 \(i, j\)의 LCP는 정렬 순위 구간
\([\text{rank}[i]+1,\ \text{rank}[j]]\)의 \(LCP\) 최솟값 과 같습니다. 이 구간
최소를 희소 테이블(sparse table)로 전처리하면 각 질의 \(O(1)\)입니다.

정리

  • LCP 인덱스가 정렬 기준이라는 점, off-by-one, 경계 검사가 3대 함정.
  • 서로 다른 부분 문자열 수·최장 반복/공통 부분 문자열이 대표 응용.
  • \(LCP\) + 희소 테이블로 임의 두 접미사 LCP를 \(O(1)\) 질의.
Practice problem Dvaput 선택 25m
COCI00030

Dvaput

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 가장 긴 반복 부분 문자열 선택 25m
R00431

가장 긴 반복 부분 문자열

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Lesson 여러 패턴을 동시에: 트라이 + 실패 링크 필수 8m

어떤 문제를 푸는가

여러 개의 패턴 \(P_1, P_2, \dots, P_k\)를 동시에 텍스트 \(T\)에서 찾습니다.
각 패턴을 KMP로 따로 돌리면 \(O(k \cdot N)\)이지만, 아호–코라식(Aho–Corasick)
은 텍스트를 단 한 번 훑어 모든 패턴의 모든 출현을 찾습니다.

$$ O\!\left(\sum_i |P_i| + N + z\right) $$

여기서 \(z\)는 (출력해야 하는) 총 출현 수입니다.

큰 그림: 트라이 + 실패 링크

아호–코라식은 두 아이디어의 결합입니다.

  1. 트라이: 모든 패턴을 한 트라이에 넣는다. 텍스트를 읽으며 트라이를 따라
    내려간다.
  2. 실패 링크(접미사 링크): 다음 글자에서 갈 자식이 없을 때, KMP의 실패
    함수처럼 "현재까지 읽은 접미사 중 트라이에 존재하는 가장 긴 것"으로 점프한다.

즉 아호–코라식은 여러 패턴판 KMP 입니다. KMP의 \(\pi\)가 하나의 패턴 내부
자기 닮음이라면, 여기서는 트라이 위의 실패 링크가 그 역할을 합니다.

세 종류의 링크

  • goto(자식) 링크: 노드에서 글자 \(c\)로 가는 트라이 간선.
  • 실패(fail) 링크: 자식이 없을 때 점프할 곳 — 루트 방향의, 현재 접미사인
    가장 긴 다른 접두사 노드.
  • 출력(output/dictionary) 링크: 실패 링크를 타고 올라가며 만나는, 단어가
    끝나는 노드들. 한 위치에서 여러 패턴이 동시에 끝날 수 있으므로 필요합니다.

실패 링크 만들기 (BFS)

실패 링크는 루트에서 가까운 노드부터, 즉 BFS 순서로 계산합니다. 노드 \(u\)의
부모가 \(p\), 간선 글자가 \(c\)일 때, \(u\)의 실패 링크는 "\(p\)의 실패 링크에서 글자
\(c\)로 간 곳"입니다. 이 규칙이 성립하려면 얕은 노드가 먼저 처리돼 있어야 하므로
BFS가 자연스럽습니다.

깊이 \(1\) 노드(루트의 자식)의 실패 링크는 모두 루트입니다.

작은 예제

패턴 {"he", "she", "his", "hers"} 를 트라이에 넣습니다. 텍스트를 읽다가
s → h → e 로 "she" 노드에 도달하면, 그 노드의 실패 링크는 "he" 노드를
가리킵니다(접미사 "he" 가 다른 패턴이므로). 따라서 "she" 가 끝나는 순간
출력 링크를 타고 "he" 의 출현도 함께 보고됩니다. 한 위치에서 두 패턴이 동시에
끝나는 상황을 출력 링크가 처리합니다.

복잡도

  • 트라이 구축: \(O(\sum |P_i|)\).
  • 실패·출력 링크 BFS: \(O(\sigma \cdot \text{노드수})\) (또는 goto를 완전 자동자로
    채우면 텍스트 매칭이 상수 이동).
  • 텍스트 매칭: \(O(N + z)\).

정리

  • 여러 패턴을 한 트라이에 넣고 실패 링크로 KMP를 일반화한다.
  • goto·fail·output 세 링크를 이해하면 구현이 명확해진다.
  • 실패 링크는 BFS로, 부모의 실패 링크를 이용해 계산한다.

다음 강의에서 구현과 응용을 봅니다.

Lesson 아호–코라식 구현 — 자동자·출력 링크 선택 8m

표준 구현 (C++, 소문자 26)

goto 링크를 완전 자동자로 채우는 방식입니다. nxt[u][c] 를 모든 \(c\)에
대해 채워 두면(자식이 없으면 실패 링크의 이동으로 대체), 텍스트 매칭이 매
글자 상수 시간이 되어 깔끔합니다.

#include <bits/stdc++.h>
using namespace std;

struct AhoCorasick {
    struct Node {
        int nxt[26];
        int fail = 0;
        int out = -1;          // 이 노드에서 끝나는 패턴 id (없으면 -1)
        int dict = 0;          // 출력 링크: 단어가 끝나는 가장 가까운 fail 조상
        Node() { fill(nxt, nxt + 26, -1); }
    };
    vector<Node> t;
    AhoCorasick() { t.emplace_back(); }   // 0 = 루트

    void insert(const string& s, int id) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[cur].nxt[c] == -1) { t[cur].nxt[c] = t.size(); t.emplace_back(); }
            cur = t[cur].nxt[c];
        }
        t[cur].out = id;
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < 26; c++) {
            int &v = t[0].nxt[c];
            if (v == -1) v = 0;                 // 루트의 빈 간선은 자기 자신
            else { t[v].fail = 0; q.push(v); }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            // 출력 링크: fail이 단어면 그 노드, 아니면 fail의 dict
            int f = t[u].fail;
            t[u].dict = (t[f].out != -1) ? f : t[f].dict;
            for (int c = 0; c < 26; c++) {
                int v = t[u].nxt[c];
                if (v == -1) t[u].nxt[c] = t[t[u].fail].nxt[c];  // 자동자화
                else { t[v].fail = t[t[u].fail].nxt[c]; q.push(v); }
            }
        }
    }

    // 텍스트에서 각 패턴의 출현 위치(끝 인덱스) 수집
    // 반환: 방문한 노드마다 out/dict 링크를 따라 끝나는 패턴들
    void match(const string& text, function<void(int pos, int id)> report) {
        int cur = 0;
        for (int i = 0; i < (int)text.size(); i++) {
            cur = t[cur].nxt[text[i] - 'a'];      // 완전 자동자라 항상 유효
            if (t[cur].out != -1) report(i, t[cur].out);
            for (int d = t[cur].dict; d != 0; d = t[d].dict)
                if (t[d].out != -1) report(i, t[d].out);
        }
    }
};

build 에서 goto를 자동자로 채운 덕분에 match 는 실패 링크를 매번 타고
올라갈 필요 없이 nxt 한 번으로 이동합니다. 다만 한 위치에서 끝나는 여러
패턴을 모두 보고하려면 dict(출력 링크)를 따라가야 합니다.

파이썬 구현

from collections import deque

class Aho:
    def __init__(self):
        self.nxt = [{}]          # 노드별 글자->자식
        self.fail = [0]
        self.out = [[]]          # 노드에서 끝나는 패턴 id 목록
    def insert(self, s, pid):
        cur = 0
        for ch in s:
            if ch not in self.nxt[cur]:
                self.nxt[cur][ch] = len(self.nxt)
                self.nxt.append({}); self.fail.append(0); self.out.append([])
            cur = self.nxt[cur][ch]
        self.out[cur].append(pid)
    def build(self):
        q = deque()
        for ch, v in self.nxt[0].items():
            self.fail[v] = 0; q.append(v)
        while q:
            u = q.popleft()
            for ch, v in self.nxt[u].items():
                f = self.fail[u]
                while f and ch not in self.nxt[f]:
                    f = self.fail[f]
                self.fail[v] = self.nxt[f].get(ch, 0) if f or ch in self.nxt[0] else 0
                if self.fail[v] == v:
                    self.fail[v] = 0
                self.out[v] += self.out[self.fail[v]]   # 출력 링크 병합
                q.append(v)
    def match(self, text):
        cur = 0; res = []
        for i, ch in enumerate(text):
            while cur and ch not in self.nxt[cur]:
                cur = self.fail[cur]
            cur = self.nxt[cur].get(ch, 0)
            for pid in self.out[cur]:
                res.append((i, pid))
        return res

파이썬판은 맵 기반이라 build/match 에서 실패 링크를 직접 타고 올라갑니다.
out[v] += out[fail[v]] 로 출력 링크를 미리 병합해 매칭을 단순화했습니다.

정리

  • goto를 완전 자동자로 채우면 매칭이 매 글자 상수 이동으로 깔끔해진다.
  • 한 위치에서 끝나는 여러 패턴은 출력(dict) 링크로 모두 수집한다.
  • BFS에서 부모의 실패 링크(또는 자동자 간선)를 재사용해 자식의 실패 링크를 정한다.
Lesson 심화·변형 — 등장 횟수, 금지 패턴 DP 선택 8m

흔한 함정

  • 루트 처리: 깊이 \(1\) 노드의 실패 링크는 반드시 루트. 루트의 빈 간선을
    자기 자신(\(0\))으로 채워 두면 이후 로직이 일관됩니다.
  • 출력 링크 누락: "she" 안의 "he" 처럼 한 위치에서 여러 패턴이 끝날 수
    있습니다. 노드의 out 만 보면 안 되고 출력(dict) 링크 체인을 따라야 모든
    출현을 얻습니다.
  • 자동자화 순서: 자식의 실패 링크를 먼저 정한 뒤(부모 실패 링크의 간선 이용),
    없는 간선을 채워야 합니다. BFS 순서를 지키지 않으면 아직 안 정해진 값을 참조.
  • 자기 참조: 실패 링크가 자기 자신이 되지 않도록 주의(루트 계산 시).
  • 알파벳/메모리: 배열 노드 \(26\)을 넘는 알파벳이면 맵을, 노드가 많으면
    메모리를 신경 써야 합니다(트라이와 동일한 트레이드오프).
  • 중복 패턴: 같은 패턴이 여러 번 삽입되면 out 을 리스트/카운트로 관리해
    개수를 정확히 셉니다.

변형 1: 각 패턴의 등장 횟수 세기

매칭 중 도달한 노드마다 카운트를 \(+1\) 한 뒤, 실패 링크 트리에서 서브트리
합을 취하면 각 패턴 노드의 총 출현 횟수가 나옵니다(출력 링크를 매번 타는 대신
후처리로 한꺼번에).

// match에서 cnt[cur]++ 만 하고, 마지막에 fail 트리 위상 역순으로:
// cnt[fail[u]] += cnt[u];  (BFS 역순으로 누적)

이 방식은 \(z\)가 매우 클 때(모든 출현 나열이 과한 경우) 총 횟수만 \(O(\text{노드수})\)에
얻는 표준 기법입니다.

변형 2: 금지 패턴 필터 / DP 결합

"금지 문자열을 포함하지 않는 길이 \(L\) 문자열의 수" 같은 문제는, 아호–코라식
자동자를 상태로 삼아 DP를 돌립니다. 상태 = (현재 노드, 진행 길이), 전이 = 다음
글자로 nxt 이동. 단어가 끝나는(또는 출력 링크에 단어가 있는) 노드를 금지
상태로 두면 됩니다. 이것이 아호–코라식의 가장 강력한 응용 중 하나입니다.

변형 3: 여러 텍스트 / 온라인

자동자는 한 번만 구축하면 여러 텍스트에 재사용할 수 있습니다. 각 텍스트마다
\(O(N + z)\). 스트리밍 입력에도 현재 노드만 유지하며 글자 단위로 처리 가능합니다.

KMP·트라이와의 관계

  • 패턴이 하나면 아호–코라식의 실패 링크는 KMP의 \(\pi\)와 정확히 대응합니다.
  • 자료구조 골격은 트라이 그대로이고, 실패·출력 링크만 추가된 것입니다.
  • 따라서 트라이와 KMP를 이해했다면 아호–코라식은 그 둘의 자연스러운 합입니다.

정리

  • 함정의 핵심은 루트·BFS 순서·출력 링크 세 가지.
  • 총 출현 횟수는 실패 트리 서브트리 합으로 효율적으로.
  • 자동자를 상태로 삼는 DP(금지 패턴 계수)가 대표 고급 응용.
Practice problem 금지어를 피하는 문자열 선택 25m
R00635

금지어를 피하는 문자열

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
06
Level 7 · Specialist

Specialist

문자열 알고리즘 · Specialist 단계

0/5 완료
Lesson 모든 부분 문자열을 담는 최소 오토마톤 필수 8m

접미사 오토마톤이란

접미사 오토마톤(Suffix Automaton, SAM) 은 문자열 \(S\)의 모든 부분 문자열을
인식하는 가장 작은 결정적 유한 오토마톤(DFA) 입니다. 시작 상태에서 어떤
경로로 글자를 따라가면, 그 경로의 라벨이 곧 \(S\)의 한 부분 문자열입니다.

놀랍게도 상태 수와 간선 수가 모두 \(O(n)\)(상태 \(\le 2n-1\), 간선 \(\le 3n-4\))이고,
온라인(\(S\)를 한 글자씩 추가)으로 \(O(n)\)(또는 \(O(n\log\sigma)\))에 만들 수 있어,
접미사 트리보다 구현이 짧으면서 강력합니다.

endpos: 상태의 정체

부분 문자열 \(t\)의 endpos\((t)\)는 "\(t\)가 \(S\)에서 끝나는 모든 위치 집합"입니다.
서로 다른 부분 문자열이라도 endpos가 같으면 하나의 상태로 묶입니다. 즉

$$ \text{SAM의 한 상태} = \text{endpos가 같은 부분 문자열들의 동치류}. $$

한 동치류에 속한 부분 문자열들은 길이가 연속 구간을 이루며, 서로가 서로의
접미사 관계입니다. 그 최댓값 길이를 \(len(v)\)라 합니다.

상태 \(v\)의 suffix link \(link(v)\)는 "\(v\)의 부분 문자열 중 가장 긴 것에서,
endpos가 더 커지는(즉 다른 동치류가 되는) 가장 긴 접미사"가 속한 상태입니다.
suffix link들은 시작 상태를 루트로 하는 트리를 이룹니다. 이 트리는 endpos
집합의 포함 관계를 나타내며, 등장 횟수 계산 등 대부분의 응용에서 핵심입니다.

각 상태 \(v\)가 나타내는 부분 문자열들의 길이 범위는
\(\big(len(link(v)),\ len(v)\big]\) 입니다.

왜 선형인가

  • 상태 수: 문자를 하나 추가할 때 새 상태 \(1\)개 + (필요 시) 분할로 인한 클론 \(1\)개만
    생기므로 총 \(O(n)\).
  • 간선 수: 아모타이즈 분석으로 \(O(n)\).

이 선형성이 SAM을 매력적으로 만듭니다.

온라인 구축의 직관 (extend)

글자 \(c\)를 추가할 때:

  1. 길이 \(len(last)+1\)인 새 상태 \(cur\)를 만든다.
  2. \(last\)에서 suffix link를 타고 올라가며, \(c\) 간선이 없는 상태들에 \(cur\)로
    가는 간선을 단다.
  3. 올라가다 \(c\) 간선이 이미 있는 상태 \(p\)를 만나면, 그 도착 \(q\)가 "바로 다음
    길이"(\(len(p)+1=len(q)\))인지 검사한다.
    - 그렇다면 \(link(cur)=q\).
    - 아니면 \(q\)를 분할(clone) 한다: \(q\)의 간선을 복사하고 길이를
    \(len(p)+1\)로 줄인 클론을 만들어, 간선을 재배선하고 링크를 정리한다.

이 "분할(clone)" 단계가 SAM 구현에서 가장 섬세한 부분입니다.

작은 예제

"aba" 를 넣으면, 상태들이 부분 문자열 a, b, ab, ba, aba 등을 endpos로
묶어 표현합니다. "a" 는 위치 \(\{0, 2\}\)에서 끝나 endpos가 크고(루트 근처),
"aba" 는 \(\{2\}\)에서만 끝나 더 특수한 상태가 됩니다.

언제 쓰나

  • 서로 다른 부분 문자열의 개수/총 길이.
  • 각 부분 문자열의 등장 횟수, 사전순 \(k\)번째 부분 문자열.
  • 두(또는 여러) 문자열의 최장 공통 부분 문자열.

정리

  • SAM = 모든 부분 문자열을 인식하는 최소 DFA, 크기 \(O(n)\).
  • 상태 = endpos 동치류, \(len\)/\(link\)/\(next\)로 표현.
  • suffix link는 endpos 포함 관계 트리; 온라인 extend + clone으로 \(O(n)\) 구축.

다음 강의에서 구현과 응용을 봅니다.

Lesson SAM 구축과 등장 횟수·부분 문자열 계수 선택 8m

SAM 구축 (C++)

#include <bits/stdc++.h>
using namespace std;

struct SAM {
    struct State {
        int len, link;
        map<char,int> next;    // 알파벳이 작으면 array<int,26>로 교체(더 빠름)
    };
    vector<State> st;
    int last;

    SAM() { st.push_back({0, -1, {}}); last = 0; }   // 초기 상태

    void extend(char c) {
        int cur = st.size();
        st.push_back({st[last].len + 1, -1, {}});
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;                        // 루트까지 올라감
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;                    // q가 바로 다음 길이 -> 그대로
            } else {
                int clone = st.size();               // q를 분할
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                while (p != -1 && st[p].next.count(c) && st[p].next[c] == q) {
                    st[p].next[c] = clone;           // q로 가던 간선을 clone으로
                    p = st[p].link;
                }
                st[q].link = clone;
                st[cur].link = clone;
            }
        }
        last = cur;
    }
    void build(const string& s) { for (char c : s) extend(c); }
};

핵심 주의: st.push_back 이 벡터를 재할당할 수 있으므로 항상 인덱스로
접근합니다(st[cur]), 참조를 캐싱하지 않습니다. clone은 \(q\)의 next 를
그대로 복사하고 길이를 \(len(p)+1\)로 줄이며, link 는 \(q\)의 것을 물려받은 뒤
\(q\)와 \(cur\)의 링크를 clone으로 바꿉니다.

응용 1: 서로 다른 부분 문자열 개수

각 상태 \(v\)는 길이 구간 \((len(link(v)), len(v)]\)의 부분 문자열들을 나타내므로,
서로 다른 부분 문자열 수는

$$ \sum_{v \ne root} \big(len(v) - len(link(v))\big). $$

long long distinctSubstrings(SAM& a) {
    long long tot = 0;
    for (int v = 1; v < (int)a.st.size(); v++)
        tot += a.st[v].len - a.st[a.st[v].link].len;
    return tot;
}

응용 2: 각 부분 문자열의 등장 횟수

extend에서 만든 원본(비클론) 상태 마다 \(cnt=1\)을 준 뒤, suffix link 트리에서
자식 → 부모로 누적(len 내림차순)하면 각 상태의 등장 횟수가 나옵니다.
클론은 초기 \(cnt=0\)이어야 합니다(위치를 새로 만든 것이 아니므로).

vector<long long> occurrences(SAM& a, const vector<int>& createdOrder,
                              const vector<int>& isClone) {
    int n = a.st.size();
    vector<long long> cnt(n, 0);
    for (int v = 1; v < n; v++) if (!isClone[v]) cnt[v] = 1;
    // len 내림차순으로 정렬 후 cnt[link[v]] += cnt[v]
    vector<int> order(n); iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(),
         [&](int x, int y){ return a.st[x].len > a.st[y].len; });
    for (int v : order) if (a.st[v].link >= 0) cnt[a.st[v].link] += cnt[v];
    return cnt;   // cnt[v] = 상태 v의 부분 문자열들이 등장하는 횟수
}

(구현 시 extend에서 새 원본 상태에 cnt=1, clone에 cnt=0을 곧바로 세팅해
두는 편이 더 간단합니다.)

파이썬 구축

class SAM:
    def __init__(self):
        self.length = [0]      # len
        self.link = [-1]
        self.nxt = [{}]
        self.last = 0
    def extend(self, c):
        cur = len(self.length)
        self.length.append(self.length[self.last] + 1)
        self.link.append(-1); self.nxt.append({})
        p = self.last
        while p != -1 and c not in self.nxt[p]:
            self.nxt[p][c] = cur; p = self.link[p]
        if p == -1:
            self.link[cur] = 0
        else:
            q = self.nxt[p][c]
            if self.length[p] + 1 == self.length[q]:
                self.link[cur] = q
            else:
                clone = len(self.length)
                self.length.append(self.length[p] + 1)
                self.link.append(self.link[q])
                self.nxt.append(dict(self.nxt[q]))
                while p != -1 and self.nxt[p].get(c) == q:
                    self.nxt[p][c] = clone; p = self.link[p]
                self.link[q] = clone
                self.link[cur] = clone
        self.last = cur

정리

  • extend/clone에서 인덱스 접근·간선 재배선·링크 정리를 정확히.
  • 서로 다른 부분 문자열 수 \(= \sum (len(v)-len(link(v)))\).
  • 등장 횟수는 원본 상태 \(cnt=1\), 클론 \(0\) 후 suffix link 트리 누적.
Lesson 심화·변형 — 최장 공통 부분 문자열, k번째 선택 8m

흔한 함정

  • clone의 len/link 시점: clone은 \(len(p)+1\), link 는 \(q\)의 옛 link를
    물려받고, 그 뒤 \(q\)와 \(cur\)의 link를 clone으로 바꿉니다. 이 순서가 어긋나면
    트리가 깨집니다.
  • 원본 vs 클론 카운트: 등장 횟수 계산에서 클론에 \(cnt=1\)을 주면 과다 계수.
    클론은 새 끝 위치를 만들지 않으므로 \(0\)이어야 합니다.
  • 벡터 재할당: push_back 후 이전 참조 무효 → 인덱스로 접근.
  • 간선 재배선 조건: 두 번째 while 에서 st[p].next[c] == q 인 동안만
    clone으로 바꿉니다. 조건을 빼면 엉뚱한 간선까지 바꿔 오답.
  • 알파벳/성능: map<char,int> 는 \(O(\log\sigma)\) 상수. 소문자면
    array<int,26>(초기 \(-1\))로 바꾸면 \(O(n)\)에 훨씬 빠릅니다.
  • len 내림차순 누적: suffix link 트리 누적은 반드시 len 큰 상태부터.
    계수 정렬로 \(O(n)\)에 정렬하면 전체 선형을 유지합니다.

변형 1: 두 문자열의 최장 공통 부분 문자열

\(A\)로 SAM을 만든 뒤 \(B\)를 한 글자씩 흘려보냅니다. 현재 상태 \(v\)와 일치 길이
\(l\)을 유지하다가, 다음 글자 간선이 없으면 suffix link를 타고 올라가며
\(l = len(\text{도달한 상태})\)로 줄여 다시 시도합니다. 매 글자에서의 \(l\) 최댓값이
답입니다. 전체 \(O(|A| + |B|)\).

int longestCommon(SAM& a, const string& b) {
    int v = 0, l = 0, best = 0;
    for (char c : b) {
        while (v && !a.st[v].next.count(c)) { v = a.st[v].link; l = a.st[v].len; }
        if (a.st[v].next.count(c)) { v = a.st[v].next[c]; l++; }
        else { v = 0; l = 0; }
        best = max(best, l);
    }
    return best;
}

변형 2: 사전순 k번째 부분 문자열

각 상태에서 "그 상태 이후로 만들 수 있는 부분 문자열 수"를 DP로 세어 두고
(\(dp[v] = 1 + \sum_{c} dp[next(v,c)]\), 서로 다른 부분 문자열 기준),
시작 상태에서 글자를 사전순으로 내려가며 \(k\)가 걸리는 경로를 따라갑니다.
"서로 다른" 대신 "등장 포함"이면 상태 등장 횟수를 가중치로 씁니다.

변형 3: 부분 문자열 등장 위치/최초 등장

각 상태에 firstpos(그 상태가 처음 끝난 위치, extend 시 \(len(cur)-1\)로 기록)를
저장하면, 임의 부분 문자열의 최초 등장 위치를 상태를 따라가 얻을 수 있습니다.
모든 등장 위치는 endpos이며 suffix link 서브트리의 firstpos들로 복원합니다.

다른 접미사 구조와의 관계

  • 접미사 배열 + LCP로 풀리는 문제 다수가 SAM으로도 풀리며, SAM은 온라인·계수형
    문제(등장 횟수, 서로 다른 부분 문자열)에 특히 강합니다.
  • SAM의 suffix link 트리는 뒤집은 문자열의 접미사 트리와 대응 관계가 있습니다.

정리

  • 최장 공통 부분 문자열은 \(B\)를 흘려보내며 suffix link로 후퇴하는 \(O(|A|+|B|)\).
  • 사전순 \(k\)번째·등장 위치는 상태 DP와 firstpos/endpos로 처리.
  • clone·카운트·간선 재배선 세 지점이 정확성의 관건.
Practice problem 두 문자열의 가장 긴 공통 부분 문자열 선택 25m
R00619

두 문자열의 가장 긴 공통 부분 문자열

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 자주 나오는 부분 문자열 선택 25m
R00630

자주 나오는 부분 문자열

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
07
Level 8 · Expert

Expert

문자열 알고리즘 · Expert 단계

0/5 완료
Lesson 모든 회문 부분 문자열의 구조: eertree 필수 8m

팰린드롬 트리(eertree)란

팰린드롬 트리(palindromic tree, 별칭 eertree) 는 문자열 \(S\)에 등장하는
서로 다른 모든 회문(팰린드롬) 부분 문자열을, 각 회문을 하나의 노드로 삼아
저장하는 자료구조입니다. 놀랍게도 길이 \(n\) 문자열의 서로 다른 회문 부분 문자열은
최대 \(n\)개 뿐이라, 전체 노드 수가 \(O(n)\)입니다(두 개의 가상 루트 포함
\(n+2\)).

온라인으로 한 글자씩 추가하며 아모타이즈 \(O(n)\)(알파벳 상수 포함
\(O(n\log\sigma)\) 또는 배열이면 \(O(n\sigma)\) 최악, 실질 선형)에 만듭니다.

두 개의 루트라는 트릭

eertree에는 특별한 노드 둘이 있습니다.

  • 가상 루트(노드 \(0\)): 길이 \(-1\). 실제 회문이 아니라, 홀수 길이 회문의
    부모 역할을 하는 "상상의" 노드입니다.
  • 빈 루트(노드 \(1\)): 길이 \(0\)(빈 문자열). 짝수 길이 회문의 부모입니다.

길이 \(-1\)이라는 기묘한 값 덕분에, 어떤 글자 \(c\)를 양쪽에 붙여 만든 길이 \(1\)
회문 \(c\)가 이 가상 루트의 자식으로 자연스럽게 생깁니다. 이 트릭이 홀·짝 회문을
하나의 규칙으로 통합합니다.

노드가 가진 것

각 노드(회문) \(v\)는 다음을 가집니다.

  • \(len(v)\): 이 회문의 길이.
  • \(next(v, c)\): 이 회문의 양옆에 글자 \(c\)를 붙여 만든 회문 노드(있으면).
    즉 \(v\)가 "aba" 이고 \(c=\)c 면 "cabac".
  • \(suf(v)\) (suffix link): \(v\)의 가장 긴 진회문 접미사 노드.
    예: "abacaba" 의 suffix link는 "aba".
  • (선택) \(cnt(v)\): 등장 횟수 계산용.

글자 \(s[i]\)를 추가할 때, "현재 문자열의 접미사이면서 양옆에 \(s[i]\)를 붙여도
회문이 되는 가장 긴 회문"을 찾아야 합니다. 즉 현재 접미사 회문 \(X\)에 대해
\(s[i - len(X) - 1] = s[i]\) 인 가장 긴 \(X\)를 suffix link를 타고 내려가며 찾습니다.
가상 루트(길이 \(-1\))는 이 조건을 항상 만족시켜(\(i-(-1)-1 = i\), \(s[i]=s[i]\))
탐색이 반드시 종료됩니다 — 최소한 길이 \(1\) 회문 \(s[i]\)는 만들 수 있습니다.

작은 예제: "aba"

  • a 추가: 회문 "a" 생성(가상 루트의 자식).
  • b 추가: 회문 "b" 생성.
  • a 추가: 회문 "aba" 생성. 그 suffix link는 진회문 접미사 "a".

서로 다른 회문은 a, b, aba 로 \(3\)개이고, 노드 수는 가상·빈 루트를 더해
\(5\)개입니다. 일반적으로 서로 다른 회문 개수 = 노드 수 \(- 2\).

언제 쓰나

  • 서로 다른 회문 부분 문자열의 개수/목록.
  • 각 회문의 등장 횟수, 가장 많이 등장하는 회문.
  • 최장 회문 부분 문자열, 회문으로의 분할(회문 분해) 관련 DP.

복잡도

  • 구축: 아모타이즈 \(O(n)\) (getLink의 총 이동이 선형으로 묶임).
  • 공간: \(O(n \cdot \sigma)\)(배열 간선) 또는 \(O(n)\)(맵 간선).

정리

  • eertree는 서로 다른 회문(\(\le n\)개)을 노드로 담는 구조.
  • 길이 \(-1\) 가상 루트 + 길이 \(0\) 빈 루트가 홀·짝 회문을 통합.
  • getLink로 접미사 회문을 찾아 온라인 \(O(n)\) 구축.

다음 강의에서 구현과 응용을 봅니다.

Lesson eertree 구축과 등장 횟수 집계 선택 8m

eertree 구축 (C++, 소문자 26)

#include <bits/stdc++.h>
using namespace std;

struct Eertree {
    vector<array<int,26>> nxt;
    vector<int> len, suf, cnt;
    string s;
    int last;

    Eertree() {
        addNode(-1);   // 0: 가상 루트(길이 -1)
        addNode(0);    // 1: 빈 루트(길이 0)
        suf[0] = 0;    // 가상 루트의 링크는 자기 자신(탐색 종점)
        suf[1] = 0;    // 빈 루트의 링크는 가상 루트
        last = 1;
    }
    int addNode(int l) {
        nxt.push_back(array<int,26>{});   // 0으로 초기화
        len.push_back(l); suf.push_back(0); cnt.push_back(0);
        return (int)len.size() - 1;
    }
    // 접미사 회문 중, 양옆에 s[i]를 붙여 회문이 되는 가장 긴 것
    int getLink(int x, int i) {
        while (i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i])
            x = suf[x];
        return x;
    }
    void add(char c) {
        s.push_back(c);
        int i = (int)s.size() - 1, ci = c - 'a';
        int cur = getLink(last, i);
        if (!nxt[cur][ci]) {                 // 이 회문이 처음 등장
            int now = addNode(len[cur] + 2);
            if (len[now] == 1) suf[now] = 1; // 길이 1 회문의 링크는 빈 루트
            else suf[now] = nxt[getLink(suf[cur], i)][ci];
            nxt[cur][ci] = now;
        }
        last = nxt[cur][ci];
        cnt[last]++;                         // 이 접미사 회문이 한 번 등장
    }
    void build(const string& str) { for (char c : str) add(c); }

    int distinctPalindromes() { return (int)len.size() - 2; }  // 두 루트 제외
};

주의: addNode 가 벡터를 재할당할 수 있으니 항상 인덱스로 접근합니다.
새 노드의 suffix link는 "\(cur\)의 suffix link에서 다시 getLink한 뒤 \(c\) 간선"
으로 정해지며, 길이 \(1\) 회문만 예외적으로 빈 루트(\(1\))를 가리킵니다.

등장 횟수 집계

add 에서 매번 cnt[last]++ 하면, 그 시점의 "가장 긴 접미사 회문"만 세어집니다.
모든 회문의 실제 등장 횟수를 얻으려면 suffix link를 따라 누적해야 합니다.
노드는 생성 순서상 부모(더 짧은 접미사 회문)가 먼저 만들어지므로, 생성 역순
으로 cnt[suf[v]] += cnt[v] 하면 됩니다.

void countOccurrences(Eertree& e) {
    for (int v = (int)e.len.size() - 1; v >= 2; v--)
        e.cnt[e.suf[v]] += e.cnt[v];
    // 이제 e.cnt[v] = 회문 v의 총 등장 횟수 (v >= 2)
}

파이썬 구축

class Eertree:
    def __init__(self):
        self.nxt = [dict(), dict()]
        self.length = [-1, 0]     # 0: 가상 루트, 1: 빈 루트
        self.suf = [0, 0]
        self.cnt = [0, 0]
        self.s = []
        self.last = 1
    def get_link(self, x, i):
        while i - self.length[x] - 1 < 0 or self.s[i - self.length[x] - 1] != self.s[i]:
            x = self.suf[x]
        return x
    def add(self, c):
        self.s.append(c)
        i = len(self.s) - 1
        cur = self.get_link(self.last, i)
        if c not in self.nxt[cur]:
            now = len(self.length)
            self.length.append(self.length[cur] + 2)
            self.nxt.append(dict()); self.cnt.append(0)
            if self.length[now] == 1:
                self.suf.append(1)
            else:
                self.suf.append(self.nxt[self.get_link(self.suf[cur], i)][c])
            self.nxt[cur][c] = now
        self.last = self.nxt[cur][c]
        self.cnt[self.last] += 1
    def distinct(self):
        return len(self.length) - 2

정리

  • 두 루트 초기화(길이 \(-1\)/\(0\)), getLink, 새 노드의 suffix link 규칙이 골격.
  • 서로 다른 회문 수 = 노드 수 \(- 2\).
  • 등장 횟수는 생성 역순으로 suffix link를 따라 누적.
Lesson 심화·변형 — 회문 계수, 최다 등장, 회문 분해 선택 8m

흔한 함정

  • 가상 루트 길이 \(-1\): 이 값이 없으면 홀수 길이 회문(특히 길이 \(1\))이 만들어
    지지 않고 getLink가 종료하지 않습니다. 반드시 노드 \(0\)의 길이를 \(-1\)로.
  • 두 루트의 suffix link: \(suf[0]=0\)(자기 자신, 탐색 종점), \(suf[1]=0\).
    이를 잘못 두면 무한 루프나 오답.
  • 길이 1 회문의 링크: 새 노드 길이가 \(1\)이면 suffix link는 빈 루트(\(1\))로
    고정. 일반 규칙을 그대로 적용하면 가상 루트를 가리켜 어긋납니다.
  • 등장 횟수 누적 방향: 반드시 생성 역순(자식→부모)으로. 순서를 뒤집으면
    누적이 틀립니다.
  • 벡터 재할당: addNode 뒤 참조 무효 → 인덱스 접근.
  • 인덱스 경계: getLink의 i - len[x] - 1 < 0 검사를 빠뜨리면 음수 인덱스 접근.

변형 1: 서로 다른 회문 개수

노드 수에서 두 루트를 뺀 값입니다. 온라인으로도, 새 노드가 생길 때마다 카운터를
\(+1\) 하면 각 접두사까지의 서로 다른 회문 수를 즉시 알 수 있습니다.

$$ \#\{\text{distinct palindromic substrings}\} = (\text{노드 수}) - 2. $$

변형 2: 회문 부분 문자열의 총 개수(중복 포함)

각 위치 \(i\)를 끝으로 하는 회문 부분 문자열의 개수는, 그 위치에서 last 가
가리키는 노드의 suffix link 체인 길이(= 접미사 회문의 수)와 같습니다.
이를 위해 각 노드에 \(series\)/\(depth\) 값을 두거나, 등장 횟수 누적 후
\(\sum_v cnt(v)\) 로 총 회문 출현 수(중복 포함)를 구합니다.

변형 3: 가장 많이 등장하는 회문

등장 횟수 누적(2강) 후 \(\max_v \big(cnt(v) \times len(v)\big)\) 같은 목적함수로
"등장 횟수 × 길이가 최대인 회문"(자주 묻는 형태)을 한 번의 순회로 찾습니다.

long long bestPalindrome(Eertree& e) {
    countOccurrences(e);
    long long best = 0;
    for (int v = 2; v < (int)e.len.size(); v++)
        best = max(best, (long long)e.cnt[v] * e.len[v]);
    return best;
}

변형 4: 회문 분해(회문 factorization) DP

각 위치의 접미사 회문들을 eertree의 suffix link로 열거하면, "문자열을 회문
조각으로 최소 몇 개로 나눌 수 있는가" 같은 DP를 효율적으로 풀 수 있습니다.
고급 형태로는 series link(등차적으로 묶은 suffix link)를 써서 회문 분해
DP를 \(O(n\log n)\)에 처리하는 기법도 있습니다.

다른 회문 도구와의 비교

  • Manacher 알고리즘은 각 중심의 최장 회문 반경을 \(O(n)\)에 주지만, "서로
    다른 회문의 개수/구조"는 직접 주지 않습니다.
  • eertree는 서로 다른 회문 각각을 노드로 명시적으로 관리하므로, 회문의 개수·
    등장 횟수·분해     같은 구조적 질의에 강합니다.

정리

  • 가상 루트 길이 \(-1\), 두 루트 링크, 길이 1 예외가 정확성의 3대 지점.
  • 서로 다른 회문 수 = 노드 수 \(- 2\), 등장 횟수는 생성 역순 누적.
  • 최다 등장 회문·회문 분해 DP가 대표 응용; 구조 질의는 Manacher보다 우위.
Practice problem 메아리치는 회문 선택 25m
R00631

메아리치는 회문

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기
Practice problem 접두사마다 팰린드롬 세기 선택 25m
R00649

접두사마다 팰린드롬 세기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

Unrated 레이팅 미적용 지금 풀기