hihocoder-1419 后缀数组四·重复旋律4 求连续重复次数最多的子串-白红宇

hihocoder-1419 后缀数组四·重复旋律4 求连续重复次数最多的子串

阅读量：5017 次

发布时间：2019-06-12

本文共 2860 字，大约阅读时间需要 9 分钟。

对于重复次数，如果确定了重复子串的长度len，那重复次数k=lcp(start,start+len)/len+1。而暴力枚举start和len的复杂度是O(n^2)，不能接受。而有一个规律，若我们只枚举len的整数倍作为起始，如果将它向前移动小于len位可以构成重复次数更长的串，那么那个位置p=start-len+lcp%len。所以每次我们计算两者并求max再与ans做max即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #define LL intusing namespace std;const LL N = 100055;class SF{ //N:数组大小public: int x[N], y[N], c[N]; int Height[N], str[N], SA[N], Rank[N];//Height数组从2开始,SA记录Rank=i的下标 int slen; int m = 1050;//字符集处理大小(传入如果不是数字，需要做位移转换) bool cmp(int* r, int a, int b, int l) { return r[a] == r[b] && r[a + l] == r[b + l]; } void Suffix(int n) { ++n; int i, j, p; for (i = 0; i < m; ++i) c[i] = 0; for (i = 0; i < n; ++i) c[x[i] = str[i]]++; for (i = 1; i < m; ++i) c[i] += c[i - 1]; for (i = n - 1; i >= 0; --i) SA[--c[x[i]]] = i; for (j = 1; j <= n; j <<= 1) { p = 0; for (i = n - j; i < n; ++i) y[p++] = i; for (i = 0; i < n; ++i) if (SA[i] >= j) y[p++] = SA[i] - j; for (i = 0; i < m; ++i) c[i] = 0; for (i = 0; i < n; ++i) c[x[y[i]]]++; for (i = 1; i < m; ++i) c[i] += c[i - 1]; for (i = n - 1; i >= 0; --i) SA[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[SA[0]] = 0; for (i = 1; i < n; ++i) { x[SA[i]] = cmp(y, SA[i - 1], SA[i], j) ? p - 1 : p++; } if (p >= n)break; m = p; } int k = 0; n--; for (i = 0; i <= n; ++i) Rank[SA[i]] = i; for (i = 0; i < n; ++i) { if (k)--k; j = SA[Rank[i] - 1]; while (str[i + k] == str[j + k])++k; Height[Rank[i]] = k; //cout << k << endl; } } static const int bitlen = 25; LL lg2(LL p)//计算log2(n) { return (LL)(log(p) / log(2)); } LL dp[bitlen][N]; LL bit[bitlen]; void initRMQ()//初始化 { bit[0] = 1; for (int i = 1; i < bitlen; i++) bit[i] = 2 * bit[i - 1]; for (int i = 0; i <= slen; i++) dp[0][i] = Height[i]; dp[0][0] = dp[0][1] = 0; for (LL i = 1; bit[i] < slen + 1; i++) for (LL j = 0; j + bit[i] <= slen + 1; j++) dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + bit[i - 1]]); } LL query(LL l, LL r)//查询两个Rank之间的lcp { if (r == l) return slen - SA[l]; if (l > r) swap(l, r); l++; LL mig = lg2(r - l + 1.0); return min(dp[mig][l], dp[mig][r - bit[mig] + 1]); } void init(string &s) { slen = s.size(); for (int i = 0; i < slen; i++) str[i] = s[i] - 'a' + 2;//如果是字符，映射成从1开始的序列 str[slen] = 1;//1作为结束符，防止越界 Suffix(slen); initRMQ(); } int solve() { int ans = 0; for (int len = 1; len <= slen; len++) { for (int i = 0; i+len < slen; i+=len) { int r1 = Rank[i], r2 = Rank[i+ len]; int lcp = query(r1, r2); ans = max(ans, lcp / len + 1); if (i - len + lcp%len >= 0) { lcp = query(Rank[i - len + lcp%len], Rank[i + lcp%len]); ans = max(ans, lcp / len + 1); } } } return ans; }}sf;int main(){ cin.sync_with_stdio(false); string s; while (cin >> s) { sf.init(s); cout << sf.solve() << endl; } return 0;}

转载于:https://www.cnblogs.com/LukeStepByStep/p/7570138.html

你可能感兴趣的文章