2. 문자열

문자열

빠른 설명

문자열은 문자들의 순서 있는 배열이다. 알고리즘 문제에서는 인덱싱, 슬라이싱, 빈도 세기, 부분 문자열 검색, 정렬, 뒤집기 등이 자주 나온다.

언제 쓰는가

• 회문, 사전순, 접두사, 접미사 문제
• 특정 문자의 개수나 위치를 세는 문제
• 문자열을 규칙대로 변환하거나 복원하는 문제

시간복잡도

• 길이 $N$ 문자열 한 번 순회: $O(N)$
• 단순 부분 문자열 검색: 최악 $O(NM)$
• KMP 검색: $O(N+M)$

참고자료

• Wikipedia - String searching algorithm
• cppreference - std::basic_string
• Python - Text Sequence Type str
• GeeksforGeeks - String Data Structure

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    string s = "abacaba";
 
    cout << s[0] << '\n';           // 첫 문자
    cout << s.substr(2, 3) << '\n'; // 2번 인덱스부터 3글자
 
    int cnt = 0;
    for (char c : s) {
        if (c == 'a') cnt++;
    }
    cout << cnt << '\n';
}

Python 코드

s = "abacaba"
 
print(s[0])
print(s[2:5])
 
cnt = 0
for ch in s:
    if ch == "a":
        cnt += 1
 
print(cnt)