有没有这样一种算法,字符串中寻找出现频率最高的子串,100分送上
。
1.对于单字符(char)先不考虑(比如A,B,C,D);
2.如何找出最大长度的重复(字符串出现的次数大于1)子串,比如图中的(ABC出现了2次)
3.如何找出重复次数最多的子串,比如图中的BC。
最好是C#语言实现,算法尽量精炼 字符串查找 重复次数
[解决办法]
如果要最快的方法的话,你需要一个叫后缀树的数据结构。一般情况O(nlogn),固定字典大小则O(n)。
不管速度的话,把n个前缀子串放在一起构造字典树然后统计频度就可以了。O(n^2)
[解决办法]
最长重复子串:KMP或者后缀数组,已经有模板了,自己搜一下嘛!
最多重复子串:将原串a[]分拆为n-1个形如a[i,...(n-1)]的子串(0<=i<n-1)来构造字典树,然后统计结点频率。
[解决办法]
trie 树
[解决办法]
统计每个单字符出现的次数,并且记录每次出现的索引,然后,从次数最多的开始统计,比如B出现5次A出现4次,然后根据A和B的索引,判断AB是否是连续串,瞎想的