关于腾讯的那道题截取字符串的题
记得是前阵子去腾讯面试时的那道题，当时用笔我没写出来，就大概说了下思路，今天有空，就写了一下，发现要做到完美还是很麻烦的。
题目是:
假设有"123<em>abc</em>456<em>def</em>789"这么一个字符串,写一个函数，可以传入一个字符串，和一个要截取的长度。返回截取后的结果。
要求:
1 <em>和</em>标记不得计算在长度之内。
2 截取后的字符串，要保留原有<em>标签，不过如果最后有一个标签没有闭合，则去掉其开始标签。
示例:
题中的字符串，要截取长度5，则返回的字符串应该为:123ab,要截取长度8，应返回123<em>abc</em>45。
我的做法大概思路是:
1 首先顺序读取字符串，并用一个resultstr变量来记录所有字符，当发现<标记时，开始将这个子字符串用tag变量记录下来。
2 如果发现tag变量形式为<\w+>也就是html标签的开始标记)，就将其入栈。用栈结构来存储这个标记。若遇到<\/\w+>(html标签的结束标记)，就出栈。
3 否则如果是常规字符的话，长度计数器++。直到与传入的要截取长度相等。
4 最后判断栈是否为空，如果为空，直接返回截取后的字符串，否则，将栈中剩余元素一个个出栈，循环从截取后的字符串中查找栈顶标签元素最后一次出现的位置，返回索引，将这个标签替换为空。直到整个栈为空为止。最后返回处理后的字符串。
原题其实是没有考虑标签嵌套的情况的，我尽量的让程序可以处理嵌套标签，使其更健壮。并且尽量少的去用php的内置函数，因为那样可能会掩盖算法本身。如可以处理a1<p>b2<em>c3</em>d4</p>e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1<p>b2<em>c3d4</p>e5的话，程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较，而没有去循环搜索整个栈。这里要改一下其实也可以。
不知大家还有没有其他思路，我感觉我这么做实在是太麻烦了，罗罗嗦嗦一大堆。这么多代码面试时拿笔写非得疯了不可。而且这个时间复杂度不理想，大概为O(n*(n2))。空间方面也占了很多多余的空间。我相信一定有很简单的办法。希望大家一起想想有什么更简单的方法没？
<?phpfunction mySubstr( $str, $length ){ $tagcnt = 0; $charcnt = 0; $tag = ''; $maxlen = strlen( $str ); $resultstr = ''; $tagstack = array(); for( $i = 0; $i < $length; $i++ ){ if( $str[$i] == '<' ){ $resultstr .= $str[$i]; for( $j=$i; $str[$j]!='>'; $j++,$length++ ){ $tag .= $str[$j]; } $tagcnt++; $length++; $tag .= '>'; //如果是开始标记，则入栈，如果是与之相对应的结束标记则出栈 if( preg_match('/<([^\/]+)?>/i', $tag, $r) ){ echo '入栈:',htmlspecialchars($r[1]),'<br />'; array_push($tagstack, $r[1]); } elseif( preg_match( '/'.$tagstack[count($tagstack)-1].'/', $tag ) ){ echo '出栈:',htmlspecialchars($tagstack[count($tagstack)-1]),'<br />'; array_pop( $tagstack ); } $tag = ''; continue; } $charcnt++; $resultstr .= $str[$i]; } echo '<hr size=1>最后结果为:'; //栈是空的直接返回 if(empty($tagstack)){ return $resultstr; } //否则去掉没有结束标记的开始标记 else{ while(!empty($tagstack)){ $tag = array_pop($tagstack); $index = strrpos($resultstr, $tag); for($i = $index-1; $resultstr[$i] != '>'; $i++ ){ $resultstr[$i] = ''; } $resultstr[$i++] = ''; } return $resultstr; } }$sttime = microtime(true);$stmem = memory_get_usage();$str = "a1<body>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";echo '处理结果为:<br/><hr size=1>',htmlspecialchars( mySubstr( $str, 18 ) ),'<br />';echo "内存使用情况:",(memory_get_usage()-$stmem),'<br />';echo "算法运行时间(microtime):",(microtime(true)-$sttime),'<br/>';$str = "a1<body>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);foreach($arr AS $k => $v){ if(isset($arr[$k+1])) { $temp = $arr[$k][1] + strlen($arr[$k][0]); $arr[$k][2] = substr($str, $temp, $arr[$k+1][1] - $temp); }}print_r($arr);/*经过这么处理后，字符串变成了由html标签 + 这个标签之前的字符 组成的元素 组成的数组。。如下Array( [0] => Array ( [0] => a1 [1] => 0 [2] => <body> ) ……*/
[解决办法]
这个题：
如果只考虑"123<em>abc</em>456<em>def</em>789"这个字符串
问题可以简单很多。
这就是只考一下你的算法
但不具实际应用意义，具有实际应用意的话就是标签不限，不是一下两个能解决的
[解决办法]
/** * 函数名 html_substr * 功能 从html串中截取指定长度的字串，html标记不计算在内 * 参数 * $str 要截取的串 * $len 要截取的长度 * $mode 不匹配的标记的处理方式 0 删去(默认)，1 补齐 * 返回 截取到的串 * 说明 * 未考虑多字节字符，仅已字节做计数单位 * 未考虑可单独存在的标记 **/function html_substr($str, $len, $mode=0) { $ar= preg_split('/(<\!--.*-->|<[^>]*>)/s', $str, -1, PREG_SPLIT_DELIM_CAPTURE); foreach($ar AS $k => $v) { if($v{0} != '<') { $len = $len - strlen($v); if($len < 0) $ar[$k] = substr($v, 0, $len); }else $ar[$k] = strtolower($v); if($len <= 0) break; } $ar = array_slice($ar, 0, $k+1); $len = count($ar); foreach($ar as $k=>$v) { if($v{0} == '<' && $v[1] != '/') { $ch = str_replace('<', '</', $v); for($i=$k+1; $i<$len && $ar[$i]!=$ch; $i++); if($i == $len) if($mode) $ar[$len] = $ch . $ar[$len]; else $ar[$k] = ''; } } return join('', $ar);}$str = "123<em>abc</em>456<em>def</em>789";echo '<xmp>';echo html_substr($str, 5) . PHP_EOL;echo html_substr($str, 5, 1);
[解决办法]
$str = "a1<body>b2c3<p><em>d4</em>e</p>5f6</body>g7h8";$gn = 7;$i = $j = $k = 0;while( ($c = $str[$i++]) && $j < $gn ) { if( $c == '<') { $tag = 1; } elseif($c == '>') { if(trim($tg,'/') == 'em') { $tgs[$j-1] = '<'.$tg.'>'; } else { if($tgs[$j-1]) $ogs[$j-1] = '1|'.'<'.$tg.'>'; else $ogs[$j-1] = '0|'.'<'.$tg.'>'; } $tag = 0; $tg = ''; } elseif($tag == 1) { $tg .= $c; } else { $tmp[] = $c; $j++; }}$ts = count($tgs);if($ts % 2) array_pop($tgs);foreach($tmp as $k=>$v){ $ba = explode('|',$ogs[$k],2); if( $tgs[$k] && $ogs[$k]) { if($ba[0]) { $s .= $v.$tgs[$k].$ba[1]; } else $s .= $v.$ba[1].$tgs[$k]; } else $s .= $v.$tgs[$k].$ba[1];}echo htmlspecialchars($s);
[解决办法]
我这里有啊....
http://hi.baidu.com/lael80/blog/item/669ebe1e50f635134134172c.html
//tags : 字符串可能包含的HTML标签//zhfw : 用来修正中英字宽参数function wsubstr($str, $length = 0, $suffixStr = "...", $start = 0, $tags = "div|span|p", $zhfw = 0.9, $charset = "utf-8"){//author: lael//blog: http://hi.baidu.com/lael80$re['utf-8'] = "/[\x01-\x7f]|[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";$re['gb2312'] = "/[\x01-\x7f]|[\xb0-\xf7][\xa0-\xfe]/";$re['gbk'] = "/[\x01-\x7f]|[\x81-\xfe][\x40-\xfe]/";$re['big5'] = "/[\x01-\x7f]|[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";$zhre['utf-8'] = "/[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";$zhre['gb2312'] = "/[\xb0-\xf7][\xa0-\xfe]/";$zhre['gbk'] = "/[\x81-\xfe][\x40-\xfe]/";$zhre['big5'] = "/[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";//下面代码还可以应用到关键字加亮、加链接等，可以避免截断HTML标签发生//得到标签位置$tpos = array();preg_match_all("/<(".$tags.")([\s\S]*?)>|<\/(".$tags.")>/ism", $str, $match);$mpos = 0;for($j = 0; $j < count($match[0]); $j ++){$mpos = strpos($str, $match[0][$j], $mpos);$tpos[$mpos] = $match[0][$j];$mpos += strlen($match[0][$j]);}ksort($tpos);//根据标签位置解析整个字符$sarr = array();$bpos = 0;$epos = 0;foreach($tpos as $k => $v){$temp = substr($str, $bpos, $k - $epos);if(!empty($temp))array_push($sarr, $temp);array_push($sarr, $v);$bpos = ($k + strlen($v));$epos = $k + strlen($v);}$temp = substr($str, $bpos);if(!empty($temp))array_push($sarr, $temp);//忽略标签截取字符串$bpos = $start;$epos = $length;for($i = 0; $i < count($sarr); $i ++){if(preg_match("/^<([\s\S]*?)>$/i", $sarr[$i]))continue;//忽略标签preg_match_all($re[$charset], $sarr[$i], $match);for($j = $bpos; $j < min($epos, count($match[0])); $j ++){if(preg_match($zhre[$charset], $match[0][$j]))$epos -= $zhfw;//计算中文字符}$sarr[$i] = "";for($j = $bpos; $j < min($epos, count($match[0])); $j ++){//截取字符$sarr[$i] .= $match[0][$j];}$bpos -= count($match[0]);$bpos = max(0, $bpos);$epos -= count($match[0]);$epos = round($epos);}//返回结果$slice = join("", $sarr);//自己可以加个清除空html标签的东东if($slice != $str)return $slice.$suffixStr;return $slice;}
[解决办法]
用数据结构来考虑这道题
struct Node_t
{
char *pdata;//动态申请内存保存字符串，也可以直接指向源字符串地址,不包含<>
int nLen;//字符串长度，不包含<>
}
struct Node
{
int flag;//统计不匹配情况，为0时表示完全匹配，开始下一个layer
Node_t *p_next;//下一个嵌套节点
Node *p_next_layer;//下一个完整节点开始
}
如上结构，如果遇到不匹配的情况，flag＋＋，同时开始新的嵌套节点，当flag为0时，开始新的node。到达指定长度后，根据节点重构字符串，如果该node的flag为0，每个node_t的字符串都要加上<>,如果不为0，则都不加上。
重构步骤，根据实际需求确定。
[解决办法]
提供下用C写的思路（PHP不会）：
建立一个结构体
node {
string key; //关键字:em,html,and so on;
int start; //start of the key;
int end; //end of the key;
int length; //the total length of the string:
//node[i+1].length = node[i].length+length;
}node[MAX];
1.首先对各个关键字进行匹配，其实就相当于括号匹配问题：遍历字符串，遇到"<"入栈，此时记录该关键字，以及起始位置：node[i].key、node[i].start；遇到"</"出栈，记录关键字的结束位置：node[i].end; 时间效率：O（N）
2.根据要输出的字符串长度nlength，遍历node.length（2分搜也可以，初始化是就是从小到大的顺序，关键是看关键字数量），可以大概判断出输出字符串到何处结束，如果该节点的node.length > nlength，则该节点的关键字就不输出（因为无法满足关键字的匹配）; 时间效率：O（nlgn）(n为关键字数量 << N)
思路大概就是这样，具体细节就看个人了；
该方法可以实现嵌套的输出；