关于字符串的一个算法请教

Question

假设我有这么一段字符串:
asda2121ffasas你好你好啊你好你好你好啊22111000csdnsdn上面这个字符串处理后应该为:
asda2121ffasas你好你好啊你好你好啊221100csdnsdn
也就是说:
在这段字符串中，任何连续出现的字符或子字符串，不能大于两次，否则就只显示两次。最差的算法应该是把字符串一层层便利，得出每一个字符及子字符串所出现的次数，有大于2的加以处理。但如果这个字符串很长的话，效率实在太低了。请教优化算法。谢谢。
其实这是我们网站的策划给我提的一个需求，因为有很多网友在留言的时候总是写一些重复的留言，他想让这些留言只显示一定次数多余的就不显示了。这个需求我已经给他打回去了，因为如果按照最差的算法效率实在太低，但还是想知道有没有什么比较高效的算法。

Answer 1

分词之后， 再去一个个遍历字符串， 基本上和你所说的很不效率， 如果放在服务器更是要命， 假使你真的想实现这个方法， 建议你把它放在客户端用JS实现。当用户在编辑文本时， 监测到对方不判断ctrl+c和ctrl+v， 你就给它不停弹窗口，“哥们， csdn不可以灌水， 不可以回复内容太短噢 ... $&^#%&*(... ”

Answer 2

$s = 'asda2121ffasas你好你好啊你好你好你好啊22111000csdnsdn ';
echo preg_replace('/(.+)\\1+/', '$1$1', $s);out:
asda2121ffasas你好你好啊你好你好啊221100csdnsdn
$s = 'asda2121ffasas你好你好啊好啊好啊你好你好你好啊22111000csdncsdncsdnsdn ';
echo preg_replace('/(.+)\\1+/', '$1$1', $s);out:
asda2121ffasas你好你好啊好啊好啊你好你好啊221100csdncsdnsdn 

Answer 3

这个算法没那么简单吧。O(n)估计没戏。
唠叨例子的第二次结果里出现了3次'好啊'了。
即使加入中文正则匹配
问题还有类似这样的
$str = '221112211122111';//'22111' 3次，'1' 3次
最终处理结果希望是什么样？22112211?

Answer 4

一个正则处理不了 
$s = 'asda2121fffsfffsfffsasas你好你好啊好啊好啊你好你好你好啊22111000csdncsdncsdnsdn';
这种情况补充一下：$s = 'asda2121fffsfffsfffsasas你好你好啊好啊好啊你好你好你好啊22111000csdncsdncsdnsdn'; $s = preg_replace('/(.+)\\1+/', '$1$1', preg_replace('/(.)\\1+/', '$1$1', $s));echo $s;

Answer 5

phpBoy005同学
用你的正则处理这样的串试试.$s = '111222333111222333111222333111222333';可以考虑写个while循环，不过这样估计效率比lz的方案差不了多少。

Answer 6

再补充$s = '111222333111222333111222333111222333';$s = preg_replace('/(.+)\\1{2,}/', '$1$1', preg_replace('/(.)\\1+/', '$1$1', $s));echo $s;

Answer 7

再测测看//$s = '111222333111222333111222333111222333';$s = '101010101010101011110001110101010101010101010101011110001111001001';$s = preg_replace('/(.+?)\\1{2,}/', '$1$1', preg_replace('/(.)\\1+/', '$1$1', $s));
echo $s;

Answer 8

to 20F
$s = '我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我';$s = preg_replace('/(.+?)\\1{2,}/', '$1$1', preg_replace('/(.)\\1+/', '$1$1', $s));
echo $s;//output
//我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我

Answer 9

//$s = '111222333111222333111222333111222333';//$s = '101010101010101011110001110101010101010101010101011110001111001001';//$s = '212121112121211121212111212121112121211121212111';$s = '我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我';
function pregMatch($str)
{
$str = preg_replace('/(.+?)\\1{2,}/', '$1$1',$str); if(preg_match('/(.+?)\\1{2,}/', $str))
{
$str = pregMatch($str);
}

return $str;
}echo pregMatch($s);

Answer 10

首先谢谢各位帮忙，我一会儿逐一测试下。因为可能还有未知的情况出现。我想了一种算法，我觉得理论上可以实现，代码还没写完。中英文字符混合也考虑进去，汉字按GBK双字节计算。
1 首先第一步，将字符串按汉字和字符拆出存放到新的数组$str = 'ab测试测试测试一下这个字字字字符串cdddd';
$len = strlen($str);//将字符串装入数组
for($i=0;$i<$len;$i++){
//如果是中文字符，就两个字节装到一个元素中
if(preg_match('/[\x7f-\xff]/i',$str[$i])){
if(($i+1) % 2 == 0){
$arr[] = $t.$str[$i];
continue;
}
$t = $str[$i];
}
//否则直接装
else{
$arr[] = $str[$i];
}
}得出这样的一个数组:
Array ( [0] => a [1] => b [2] => 测 [3] => 试 [4] => 测 [5] => 试 [6] => 测 [7] => 试 [8] => 一 [9] => 下 [10] => 这 [11] => 个 [12] => 字 [13] => 字 [14] => 字 [15] => 字 [16] => 符 [17] => 串 [18] => c [19] => d [20] => d [21] => d [22] => d )
第二步:统计字符或汉字出现次数我前面说了，要求连续重复的字符或子字符串<=2次。现在归纳一下已知条件:
1 相同字符连续出现次数<=2
2 重复出现的字符或汉字即使不连续，但并不代表以他组成的词不是连续出现的。比如"你好你好",虽然你和好都不连续出现，但组成词，他们就是连续的。
统计出上面字符串中每个字符出现的次数:
Array ( [a] => 1 [b] => 1 [测] => 3 [试] => 3 [一] => 1 [下] => 1 [这] => 1 [个] => 1 [字] => 4 [符] => 1 [串] => 1 [c] => 1 [d] => 4 )接下来对于重复出现的单字，我把它放到新数组，并且最多只放两个。Array ( [0] => a [1] => b [2] => 测 [3] => 试 [4] => 测 [5] => 试 [6] => 一 [7] => 下 [8] => 这 [9] => 个 [10] => 字 [11] => 符 [12] => 串 [13] => 字 [14] => 字 [15] => 符 [16] => 串 [17] => 字 [18] => 符 [19] => 串 [20] => c [21] => d [22] => d )第三步:合并
将索引相邻的两个元素合并，组成词，再放到一个新数组中，然后我再去判断是否有连续出现次数>2的词。接下来是一个循环合并的过程，合并的次数不超过整个字符串的一半。合并之后放在数组中，变成了下面这样
Array ( [0] => ab [1] =>测试  [2] =>测试  [3] =>一下  [4] =>这个  [5] =>字符  [6] =>串字  [7] =>字符  [8] =>串字  [9] =>符串  [10] =>cd  [11] =>d )之后我再遍历数组，将索引连续的，重复出现次数>2的词放入新数组合并。不过这次合并需要前一个元素与后面的半个元素进行合并。否则[0]和[1]合并就变成了[0] =>ab测试，而我们想要的是[0] =>ab测。然后就进入这个一个合并->处理的循环过程，合并次数为字符串总长度的一半。
我觉得这种思路可以最终实现，但空间复杂度有点过高。

Answer 11

方法肯定是有，但就算以上面的方法来处理，当字符串到达一定长度，对性能的消耗依然很高。放在服务器端对服务器的cpu有影响，放在客户端也许他的浏览器直接就卡死了。所以在没有找到很高效算法前，肯定不能实际应用。我现在其实只是想知道是否有简单方法解决这个问题，至于他放在客户端或服务器端可以不考虑这些。

Answer 12

#23楼的思路回到while循环那去了,呵呵.
就如我#9想的一样.等同于
$s = '我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我.我是你你是我我是你你是我我是你你是我';$str = preg_replace('/(.+?)\\1{2,}/', '$1$1',$s);
while(preg_match('/(.+?)\\1{2,}/', $str))
{
$str = preg_replace('/(.+?)\\1{2,}/', '$1$1',$str);
}
echo $str;
LZ的思路没怎么看明白,感觉合并那个过程要很费时间,因为两两相邻合并有两种组合(数组当前元素和前面的元素合并一种,当前元素和后面的元素合并又是另一种),以此类推数组三个相邻元素合并又有多种.这么下去n个元素合并,那得判断多少种组合下,有相邻的字符串..
也很可能是没看清楚LZ的思路.

Answer 13

建议ShadowSniper去'数据结构与算法'板块问问那些搞算法的家伙,说不定有成熟的解决方案,正则可能不是最优方案.