关于字符串的一个算法请教
假设我有这么一段字符串:
asda2121ffasas你好你好啊你好你好你好啊22111000csdnsdn
上面这个字符串处理后应该为:
asda2121ffasas你好你好啊你好你好啊221100csdnsdn
也就是说:
在这段字符串中，任何连续出现的字符或子字符串，不能大于两次，否则就只显示两次。
最差的算法应该是把字符串一层层便利，得出每一个字符及子字符串所出现的次数，有大于2的加以处理。但如果这个字符串很长的话，效率实在太低了。请教优化算法。谢谢。
其实这是我们网站的策划给我提的一个需求，因为有很多网友在留言的时候总是写一些重复的留言，他想让这些留言只显示一定次数多余的就不显示了。这个需求我已经给他打回去了，因为如果按照最差的算法效率实在太低，但还是想知道有没有什么比较高效的算法。
------解决方案--------------------
分词之后， 再去一个个遍历字符串， 基本上和你所说的很不效率， 如果放在服务器更是要命， 假使你真的想实现这个方法， 建议你把它放在客户端用JS实现。
当用户在编辑文本时， 监测到对方不判断ctrl+c和ctrl+v， 你就给它不停弹窗口，“哥们， csdn不可以灌水， 不可以回复内容太短噢 ... $&^#%&*(... ”
------解决方案--------------------
$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
------解决方案--------------------
这个算法没那么简单吧。O(n)估计没戏。
唠叨例子的第二次结果里出现了3次'好啊'了。
即使加入中文正则匹配
问题还有类似这样的
$str = '221112211122111';//'22111' 3次，'1' 3次
最终处理结果希望是什么样？22112211?
------解决方案--------------------
#23楼的思路回到while循环那去了,呵呵.
就如我#9想的一样.等同于
- PHP code
$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;