Repeats SPOJ - REPEATS(后缀数组解决重复次数最多的连续重复子串)

标签：cal   char   公共前缀   +=   scanf   --   char s   poj   情况   

题目链接
题意：给定一个字符串，求重复次数最多的连续重复子串
题目思路：先穷举长度L，然后求长度为L的子串最多能连续出现几次。首先连续出现1次是肯定可以的，所以这里只考虑至少2次的情况。假设在原字符串中连续出现2次，记这个子字符串为S，那么S肯定包括了字符r[0], r[L], r[L2],r[L3], ……中的某相邻的两个。所以只须看字符r[Li]和r[L(i+1)]往前和
往后各能匹配到多远，记这个总长度为K，那么这里连续出现了K/L+1次。最后看最大值是多少。
穷举长度L的时间是n，每次计算的时间是n/L。所以整个做法的时间复杂度是O(n/1+n/2+n/3+……+n/n)=O(nlogn)。
用RMQ预处理区间最小值，方便求r[Li]和r[L(i+1)]的最长公共前缀，这就是往后面匹配了多长。
对于往前面匹配了多长，我们只要看jL-(i-k%i)和(j+1)L-(i-k%i)能否算上去即可。

#include
#include
#include
#include
using namespace std;
#define Max_N 50010
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)= 0; i--) b[--ws1[wv1[i]]] = a[i]; 
	return; 
 }
void dc3(int *r, int *sa, int n, int m)
{
	int i, j, *rn = r + n, *san = sa + n,ta = 0,tb = (n + 1) / 3,tbc = 0,p; 
    r[n] = r[n+1] = 0; 
    for (i = 0; i b)
        swap(a,b);
    return Ask_MIN(a+1,b);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		char s[5];
		for(int i=0;i=0&&calprefix(k,k+i)>=i)
                    ans++;
                Max=max(Max,ans);
            }
        }
        printf("%d\n",Max);
	 } 
 }       

Repeats SPOJ - REPEATS(后缀数组解决重复次数最多的连续重复子串)

标签：cal   char   公共前缀   +=   scanf   --   char s   poj   情况   

原文地址：https://www.cnblogs.com/2462478392Lee/p/13810828.html