从一个字符串中找到一个连续子串，该子串中任何两个字符不能相同，求子串的最大长度并输出一条最长不重复子串。
PHP 算法面试题
<?php
class longest_not_repeatable_substring
{
function __construct($str)
{
$maxlen = 0;
$maxindex = 0;
/* LNRS 基本算法 hash */
$visit_key = range('a', 'z');
$visit_val = array_fill(0, 26, -1);
$visit = array_combine ($visit_key, $visit_val);
$visit[$str[0]] = 0;
$curlen = 1;
$last_start = 0;
$size = strlen($str);
for($i=1; $i<$size; $i++)
{
if($visit[$str[$i]] == -1)
{
$curlen++;
$visit[$str[$i]] = $i; /* 记录字符下标 */
}
else
{
if($last_start <= $visit[$str[$i]])
{
$curlen = $i - $visit[$str[$i]];
$last_start = $visit[$str[$i]] + 1;
$visit[$str[$i]] = $i; /* 更新最近重复位置 */
}
else
{
$curlen++;
}
}
if($curlen > $maxlen)
{
$maxlen = $curlen;
$maxindex = $i + 1 - $maxlen;
}
}
$this->output($str, $maxindex, $maxlen);
}
/* 输出LNRS */
private function output($str, $maxindex, $maxlen)
{
if($maxlen == 0)
{
echo iconv('utf-8', 'gbk', '无最长的不重复子串');
}
else
{
echo iconv('utf-8', 'gbk', '最长的不重复子串的长度为：'.$maxlen."\n其值为：\n");
$i = $maxindex;
while($maxlen--)
{
printf("%s",$str[$i++]);
}
}
printf("\n");
}
}
function read()
{
$input = trim(fgets(STDIN));
return $input;
}
function test()
{
$str = 'abcdefabcdefg';
new longest_not_repeatable_substring($str);
}
function main()
{
echo iconv('utf-8', 'gbk', "请输入字符串\n");
$str = read();
new longest_not_repeatable_substring($str);
}
if(!empty($argv[1]) && $argv[1]=='test')
{
test();
}
else
{
main();
}