====== string.py ======
  * 구버전 코드는 [[string_old]]로.



===== z_array =====

==== 코드 ====
<dkpr py>
# 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
</dkpr>

==== 설명 ====
  * z algorithm을 적용해서 z-array를 계산한다

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[string.z_array]*
csv: 0
----



===== Trie =====

==== 코드 ====
<dkpr py>
# 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:
            self.add(word)

    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)
</dkpr>

==== 설명 ====
  * [[ps:트라이]] 참고

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


===== palindrome_radiuses =====

==== 코드 ====
<dkpr py>
# N palindrome_radiuses
# I {"version": "1.01", "typing": ["Sequence", "TypeVar"], "const": ["T"]}
def palindrome_radiuses(text: Sequence[T]):
    """Implementation of Manacher's algorithm."""

    end = center = -1
    radiuses = []
    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]:
                rad += 1
                left -= 1
                right += 1
        except IndexError:
            pass
        if right > end:
            center, end = i, right
        radiuses.append(rad)
    return radiuses
</dkpr>

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

==== 이 코드를 사용하는 문제 ====
---- struct table ----
schema: ps
cols: site, prob_id, %title%, prob_level
filter: teflib ~ *[palindrome_radiuses]*
csv: 0
----