#!/usr/bin/env python3
"""A02: independent exhaustive oracles; all checks remain active under python -O."""
from collections import Counter
from itertools import product
import json
from pathlib import Path


def require(ok, message):
    if not ok:
        raise AssertionError(message)


def manacher(s):
    n = len(s)
    odd, even = [0] * n, [0] * n
    left = right = 0
    for i in range(n):
        k = 1 if i >= right else min(odd[left + right - 1 - i], right - i)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        odd[i] = k
        if i + k > right:
            left, right = i - k + 1, i + k
    left = right = 0
    for i in range(n):
        k = 0 if i >= right else min(even[left + right - i], right - i)
        while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
            k += 1
        even[i] = k
        if i + k > right:
            left, right = i - k, i + k
    return odd, even


def is_palindrome(left, right, odd, even):
    n = len(odd)
    if not 0 <= left <= right <= n:
        raise ValueError('invalid half-open interval')
    length = right - left
    if length == 0:
        return True
    center = (left + right) // 2
    return (odd[center] >= length // 2 + 1 if length % 2
            else even[center] >= length // 2)


class Eertree:
    def __init__(self):
        self.text = []
        self.length = [-1, 0]   # imaginary root 0, empty root 1
        self.link = [0, 0]
        self.next = [{}, {}]
        self.first_end = [-1, -1]
        self.as_longest = [0, 0]
        self.last = 1
        self.first_steps = self.second_steps = 0
        self.steps_by_append = []

    def _extendable(self, v, i, second=False):
        steps = 0
        while i - self.length[v] - 1 < 0 or self.text[i - self.length[v] - 1] != self.text[i]:
            v = self.link[v]
            steps += 1
        if second:
            self.second_steps += steps
        else:
            self.first_steps += steps
        return v

    def add(self, c):
        if not isinstance(c, str) or len(c) != 1:
            raise ValueError('add expects one Unicode code point')
        old_l = self.length[self.last]
        old_h = max(0, self.length[self.link[self.last]])
        before = (self.first_steps, self.second_steps)
        self.text.append(c)
        i = len(self.text) - 1
        q = self._extendable(self.last, i)
        created = c not in self.next[q]
        if created:
            v = len(self.length)
            self.length.append(self.length[q] + 2)
            self.link.append(1)
            self.next.append({})
            self.first_end.append(i)
            self.as_longest.append(0)
            self.next[q][c] = v
            if self.length[v] > 1:
                p = self._extendable(self.link[q], i, second=True)
                self.link[v] = self.next[p][c]
        self.last = self.next[q][c]
        self.as_longest[self.last] += 1
        first = self.first_steps - before[0]
        second = self.second_steps - before[1]
        new_l = self.length[self.last]
        new_h = max(0, self.length[self.link[self.last]])
        require(first <= old_l + 2 - new_l, 'first potential bound')
        require(second <= old_h + 2 - new_h, 'second potential bound')
        self.steps_by_append.append((first, second))
        return created

    def occurrences(self):
        # Copy raw counts: repeated queries must not accumulate propagation twice.
        counts = self.as_longest.copy()
        for v in range(len(counts) - 1, 1, -1):
            counts[self.link[v]] += counts[v]
        return counts

    def representative(self, v):
        end = self.first_end[v] + 1
        return ''.join(self.text[end - self.length[v]:end])


def minimum_palindrome_factorization(s):
    odd, even = manacher(s)
    n = len(s)
    dp, previous = [0] + [n + 1] * n, [-1] * (n + 1)
    for end in range(1, n + 1):
        for start in range(end):
            if is_palindrome(start, end, odd, even) and dp[start] + 1 < dp[end]:
                dp[end] = dp[start] + 1
                previous[end] = start
    intervals = []
    end = n
    while end:
        start = previous[end]
        intervals.append((start, end))
        end = start
    intervals.reverse()
    return dp, previous, intervals


def eertree_factorization(s):
    tree = Eertree()
    dp, prev, transitions = [0], [-1], 0
    for end, c in enumerate(s, 1):
        tree.add(c)
        dp.append(end + 1)
        prev.append(-1)
        v = tree.last
        while tree.length[v] > 0:
            start = end - tree.length[v]
            if dp[start] + 1 < dp[end]:
                dp[end], prev[end] = dp[start] + 1, start
            transitions += 1
            v = tree.link[v]
    return dp, prev, transitions


class CountedSequence:
    def __init__(self, text):
        self.text, self.comparisons = text, 0
    def __len__(self):
        return len(self.text)
    def __getitem__(self, i):
        owner = self
        class Symbol:
            def __init__(self, value): self.value = value
            def __eq__(self, other):
                owner.comparisons += 1
                return self.value == other.value
        return Symbol(self.text[i])


def brute_occurrences(s):
    return Counter(s[a:b] for a in range(len(s)) for b in range(a + 1, len(s) + 1)
                   if s[a:b] == s[a:b][::-1])


def brute_cut_minimum(s):
    if not s:
        return 0
    best = len(s)
    for mask in range(1 << (len(s) - 1)):
        cuts = [0] + [i for i in range(1, len(s)) if mask & (1 << (i - 1))] + [len(s)]
        pieces = [s[a:b] for a, b in zip(cuts, cuts[1:])]
        if all(x == x[::-1] for x in pieces):
            best = min(best, len(pieces))
    return best


def verify_word(s, cuts=False):
    n = len(s)
    odd, even = manacher(s)
    counted = CountedSequence(s)
    require(manacher(counted) == (odd, even), ("instrumentation", s))
    require(counted.comparisons <= 4*n, ("Manacher linear comparisons", s, counted.comparisons))
    inventory = brute_occurrences(s)
    for a in range(n + 1):
        for b in range(a, n + 1):
            require(is_palindrome(a, b, odd, even) == (s[a:b] == s[a:b][::-1]), ('query', s, a, b))
    require(sum(odd) + sum(even) == sum(inventory.values()), ('radii count', s))
    tree = Eertree()
    longest = []
    for end, c in enumerate(s, 1):
        before = brute_occurrences(s[:end-1])
        created = tree.add(c)
        now = brute_occurrences(s[:end])
        require(int(created) == len(set(now) - set(before)), ('new node', s, end))
        expected = max((s[j:end] for j in range(end) if s[j:end] == s[j:end][::-1]), key=len)
        require(tree.representative(tree.last) == expected, ('longest suffix', s, end))
        longest.append(expected)
    counts = tree.occurrences()
    got = {tree.representative(v): counts[v] for v in range(2, len(tree.length))}
    require(got == inventory, ('inventory counts', s, got, inventory))
    require(counts == tree.occurrences(), ('occurrences idempotence', s))
    require(len(tree.length) <= n + 2 and tree.first_steps <= 2*n and tree.second_steps <= 2*n, ('amortization', s))
    for v in range(2, len(tree.length)):
        p = tree.representative(v)
        require(tree.link[v] < v, ('creation order', s, v))
        candidates = [p[j:] for j in range(1, len(p)+1) if p[j:] == p[j:][::-1]]
        require(tree.representative(tree.link[v]) == max(candidates, key=len), ('suffix link', s, p))
    dp, prev, intervals = minimum_palindrome_factorization(s)
    edp, eprev, transitions = eertree_factorization(s)
    require(dp == edp and prev == eprev, ('dp independent implementations', s))
    require(transitions == sum(inventory.values()), ('suffix scan equals occurrence count', s))
    require(''.join(s[a:b] for a,b in intervals) == s and len(intervals) == dp[-1], ('reconstruction', s))
    require(all(s[a:b] == s[a:b][::-1] and a < b for a,b in intervals), ('pieces', s))
    if cuts:
        require(dp[-1] == brute_cut_minimum(s), ('all-cutsets oracle', s))
    return {'word':s,'odd':odd,'even':even,'occurrences':sum(inventory.values()),
            'distinct':len(inventory),'inventory':got,'longest_suffix_by_prefix':longest,
            'dp':dp,'previous':prev,'intervals':intervals,'pieces':[s[a:b] for a,b in intervals],
            'first_link_steps':tree.first_steps,'second_link_steps':tree.second_steps,
            'dp_transitions':transitions,'steps_by_append':tree.steps_by_append,'manacher_character_comparisons':counted.comparisons}


def main():
    words = {''.join(t) for n in range(9) for t in product('abc', repeat=n)}
    words.update(''.join(t) for n in range(12) for t in product('ab', repeat=n))
    cuts = 0
    for s in sorted(words, key=lambda x:(len(x),x)):
        verify_word(s, cuts=len(s)<=7)
        cuts += int(len(s)<=7)
    examples = [verify_word(s) for s in ['', 'a', 'aa', 'aba', 'aaba', 'abacdcabba', 'bbaabbaabbaa', '界🙂界🙂', 'a'*200+'b']]
    for bounds in [(-1,0),(0,2),(1,0)]:
        try:
            is_palindrome(*bounds,[1],[0])
        except ValueError:
            pass
        else:
            raise AssertionError('invalid interval accepted')
    result={'status':'PASS','scope':'Two radius arrays/all interval queries; incremental distinct nodes; longest suffix/link/occurrence oracles; both potential inequalities per append; independent all-cutsets minimum for short words; O mode retains every explicit check.',
            'counts':{'exhaustive_words':len(words),'all_cutset_words':cuts,'fixed_examples':len(examples)},'examples':examples}
    dest=Path(__file__).with_name('algorithms-palindrome-results.json')
    dest.write_text(json.dumps(result,ensure_ascii=False,indent=2)+'\n')
    print(json.dumps({'status':'PASS','counts':result['counts']},ensure_ascii=False))

if __name__=='__main__':
    main()