题意：给你一个串，问期中至少出现m次的最长子串及其起始位置的坐标。
思路：hash+LCP+二分答案
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn = 40000 + 10; 7 const int x = 123; 8 int n, m, pos; 9 unsigned long long H[maxn], xp[maxn]; 10 11 unsigned long long hash[maxn]; 12 int rank[maxn]; 13 14 int cmp(const int& a, const int& b) 15 { 16 return hash[a] < hash[b] || (hash[a] == hash[b] && a < b); 17 } 18 19 int possible(int L) 20 { 21 int c = 0; 22 pos = -1; 23 for(int i = 0; i < n-L+1; i++) 24 { 25 rank[i] = i; 26 hash[i] = H[i] - H[i+L]*xp[L]; 27 } 28 sort(rank, rank+n-L+1, cmp); 29 for(int i = 0; i < n-L+1; i++) 30 { 31 if(i == 0 || hash[rank[i]] != hash[rank[i-1]]) 32 c = 0; 33 if(++c >= m) 34 pos = max(pos, rank[i]); 35 } 36 return pos >= 0; 37 } 38 39 int main() 40 { 41 char s[maxn]; 42 while(scanf("%d", &m) == 1 && m) 43 { 44 scanf("%s", s); 45 n = strlen(s); 46 H[n] = 0; 47 for(int i = n-1; i >= 0; i--) 48 H[i] = H[i+1]*x + (s[i] - 'a'); 49 xp[0] = 1; 50 for(int i = 1; i <= n; i++) 51 xp[i] = xp[i-1]*x; 52 if(!possible(1)) 53 printf("none "); 54 else 55 { 56 int L = 1, R = n+1; 57 while(R - L > 1) 58 { 59 int M = L + (R-L)/2; 60 if(possible(M)) 61 L = M; 62 else R = M; 63 } 64 possible(L); 65 printf("%d %d ", L, pos); 66 } 67 } 68 return 0; 69 }