ps:teflib:string

# string.py

## z_array

### 코드

# N z_array
# I {"version": "1.0"}
def z_array(s: str) -> list[int]:
"""Returns Z array of given string. (z[0]==len(s))"""
n = len(s)
l, r, z = 0, 0, [0]
for i in range(1, n):
z_i = min(r - i + 1, z[i - l]) if i <= r else 0
while i + z_i < n and s[z_i] == s[i + z_i]:
z_i += 1
if i + z_i - 1 > r:
l, r = i, i + z_i - 1
z.append(z_i)
z[0] = n
return z

### 설명

• z algorithm을 적용해서 z-array를 계산한다

### 이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ13576Prefix와 Suffix플래티넘 2
BOJ13713문자열과 쿼리플래티넘 5
BOJ16229반복 패턴플래티넘 4
BOJ28064이민희진실버 5

## Trie

### 코드

# N Trie
# I {"version": "2.0", "typing": ["Generator", "Generic", "Iterable", "TypeVar"]}
_CharLike = TypeVar('_CharLike')
_StrLike = Iterable[_CharLike]
_TrieNode = int

class Trie(Generic[_CharLike]):
def __init__(self, words: Iterable[_StrLike] = ()):
self.ROOT = 0
self.word_counts = [0]
self.child_counts = None
self.children = [{}]
for word in words:

def add(self, word: _StrLike) -> _TrieNode:
"""Adds the given word to trie and returns a node for it."""
node = self.ROOT
for ch in word:
try:
node = self.children[node][ch]
except KeyError:
new_node = len(self.children)
self.children.append({})
self.word_counts.append(0)
self.children[node][ch] = new_node
node = new_node
self.word_counts[node] += 1
return node

def prefixes(self, word: _StrLike) -> Generator[_TrieNode, None, None]:
"""Yields all nodes for prefixes of the given word."""
node = self.ROOT
return ((node := self.children[node][ch]) for ch in word)

def nodes(self) -> Iterable[_TrieNode]:
return range(1, len(self.children))

def words(self) -> Iterable[_TrieNode]:
return (x for x in self.nodes() if self.word_counts[x] > 0)

def get_child_count(self, node: _TrieNode) -> int:
def count_rec(node):
if self.child_counts[node] is None:
self.child_counts[node] = sum(
count_rec(child) + self.word_counts[child]
for child in self.children[node].values())
return self.child_counts[node]
if not self.child_counts:
self.child_counts = [None] * len(self.children)
return count_rec(node)

### 코드

# N palindrome_radiuses
# I {"version": "1.01", "typing": ["Sequence", "TypeVar"], "const": ["T"]}
"""Implementation of Manacher's algorithm."""

end = center = -1
for i in range(len(text)):
rad = min(end - i - 1, radiuses[center * 2 - i]) if i < end else 0
left = i - rad - 1
right = i + rad + 1
try:
while text[left] == text[right]:
left -= 1
right += 1
except IndexError:
pass
if right > end:
center, end = i, right
return radiuses

### 설명

• Manacher's algorithm 을 구현한 것으로 가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring)을 참고.
• 원본 문자열을 그대로 인자로 넘겨서 돌리면 홀수 길이 팰린드롬에 대한 정보밖에 얻지 못하므로, 대부분의 경우에는 문자열의 각 문자 사이에 특수문자를 추가하는 식으로 문자열을 변형하여서 인자로 넘긴다.

### 이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ11046팰린드롬??플래티넘 5
BOJ13275가장 긴 팰린드롬 부분 문자열플래티넘 5
BOJ14444가장 긴 팰린드롬 부분 문자열플래티넘 5
BOJ16163#15164번_제보플래티넘 5
BOJ18171ABB플래티넘 4
프로그래머스12904가장 긴 팰린드롬Level 3

## 토론

댓글을 입력하세요:
R V﻿ F U V

ps/teflib/string.txt · 마지막으로 수정됨: 2023/05/27 15:23 저자 teferi