最長繰返しサブストリングアルゴリズム

要求:文字列を指定し、その最長の繰返しサブ列、例えば文字列abcdabcabcdを求め、最長の繰返しサブ列をabcdと求める.参考答案:

<?php
class longest_repeatable_substring
{
    function __construct($str)
    {
        $str_len = strlen($str);
        $maxlen = 0;
        $maxi = 0;
        $suffix_array = array();
        for($i=0; $i<$str_len; $i++)
        {
            $suffix_array[] = substr($str, $i);
        }
        sort($suffix_array);
        for($i=0; $i<$str_len-1; $i++)
        {
            $j = 0;
            while(!empty($suffix_array[$i]{$j}) && ($suffix_array[$i]{$j} == $suffix_array[$i+1]{$j}))
            {
                $j++;
            }
            if($j > $maxlen)
            {
                $maxlen = $j;
                $maxi = $i;
            }
        }
        if($maxlen > 0)
        {
            echo iconv('utf-8', 'gbk', $str.'         ： '.substr($suffix_array[$maxi], 0 ,$maxlen));
        }
        else
        {
            echo iconv('utf-8', 'gbk', '        ');
        }    
        echo "
";
    }
}

function read()
{
    $input = trim(fgets(STDIN));
    return $input;
}

function test()
{
    $str = 'abcdefhabcedfjjcdefhijk';
    new longest_repeatable_substring($str);
}

function main()
{
    echo iconv('utf-8', 'gbk', "      
");
    $str = read();
    new longest_repeatable_substring($str);    
}

if(!empty($argv[1]) && $argv[1]=='test')
{
    test();    
}
else
{
    main();
}