trie

t.php

<?php

class Trie {
    private $root;
    public function __construct()  {
        $this->root = new TrieNode;
    }

    public function addString($str, $index){
        $this->root->addString($str, $index);
    }
    public function findString($str){
        return $this->root->findString($str);
    }
    public function __toString(){
        return $this->root->__toString();
    }
}

class TrieNode {
    private $index = -1;
    private $children = array();

    public function findString($str){
        if (0 === strlen($str)){
            return $this->index;
        }
        $prefix = substr($str, 0, 1);
        if (!isset($this->children[$prefix])){
            return false;
        }
        return $this->children[$prefix]->findString(substr($str, 1));
    }

    public function addString($str, $index) {
        if (strlen($str) > 0) {
            $prefix = substr($str, 0, 1);
            if (!isset($this->children[$prefix])){
                $this->children[$prefix] = new TrieNode;
            }
            $this->children[$prefix]->addString(substr($str, 1), $index);
        } else {
            $this->index = $index;
        }
    }
    public function __toString() {
        echo 'Node<', $this->index, '>';
        foreach($this->children as $child){
            echo $child->__toString(), PHP_EOL;
        }
    }

    public function buildSuffixTrie($word) {
        $sufftrie = new Trie;
        for ($i = strlen($word) - 1; $i > -1;$i--){
            $sufftrie->addString(substr($word, $i), $i);
        }
        return $sufftrie;
    }
}

$t = new Trie;
$t->addString('aap',2);
$t->addString('aai',3);
$t->addString('paard',5);
$a = $t->findString('paard');
echo $a, PHP_EOL;
echo $t->__toString(), PHP_EOL;

t2.php

<?php
class Node {
    private $data;
    private $bros;
    private $child;
    public function __construct($x, $bros = null, $child = null){
        $this->data = $x;
        $this->bros = $bros;
        $this->child = $child;
    }
    public function getChild($x){
        $child = $this->child;
        while(null !== $child){
            if($child->data == $x){
                break;
            }
            $child = $child->bros;
        }
        return $child;
    }
    public function setChild($x){
        $child = new Node($x, $this->child);
        $this->child = $child;
        return $child;
    }
    public function delChild($x){
        $child = $this->child;
        if($child->data === $x){
            $this->child = $child->bros;
            return true;
        }
        while(null !== $child->bros){
            if($child->bros->data === $x){
                $child->bros = $child->bros->bros;
                return true;
            }
            $child = $child->bros;
        }
        return false;
    }
}
class Trie {
    protected $root;
    protected $leaf;
    public function __construct($x = null){
        $this->root = new Node(null);
        $this->leaf = $x;
    }

    public function search($sequence){
        $node = $this->root;
        foreach(str_split($sequence) as $x){
            $node = $node->getChild($x);
            if(null === $node){
                return false;
            }
        }
        $leaf = $node->getChild($this->leaf);
        if(null === $leaf){
            return false;
        }
        return $leaf;
    }

    public function insert($sequence){
        $node = $this->root;
        foreach(str_split($sequence) as $x){
            $child = $node->getChild($x);
            if(null === $child){
                $child = $node->setChild($x);
            }
            $node = $child;
        }
        $leaf = $node->getChild($this->leaf);
        if(null !== $leaf){
            $leaf->setChild($this->leaf);
        }
    }
    public function delete($sequence){
        $node = $this->root;
        foreach(str_split($sequence) as $x){
            $node = $node->getChild($x);
            if(null === $node){
                return false;
            }
        }
        return $node->delChild($this->leaf);
    }
    public function getRoot(){
        return $this->root;
    }
    public function getLeaf(){
        return $this->leaf;
    }
}

class TrieIterator implements Iterator {
    private $trie;

    private $node;
    public function __construct(Trie $trie){
        $this->trie = trie;
    }
    public function valid(){
    }
    public function rewind(){
    }
    public function current(){
    }
    public function next(){
    }
    public function key(){
    }
}

function make_suffix_trie($sequence){
    $a = new Trie;
    for($i = 0; $i < strlen($sequence); ++$i){
        $a->insert(substr($sequence, $i));
    }
    return $a;
}

$s = make_suffix_trie('abcabbca');
var_dump($s);