LA 4513 Stammering Aliens 字符串hash - c++编程基础

字符串hash模板，
本题是求，给定字符串s中至少出现m次的最长字符串长度，及此时起始位置的最大值
LA 4513 Stammering Aliens
白书p225
//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; //LOOP #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FD(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define CPY(a, b) memcpy(a, b, sizeof(a)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RS(s) scanf("%s", s) //OUTPUT #define WI(n) printf("%d\n", n) #define WS(s) printf("%s\n", s) const int INF = 0x3f3f3f3f; #define ULL unsigned long long const int maxn = 40010; const int SEED = 13331; int n, m; int rank[maxn]; char s[maxn]; ULL xp[maxn]; ULL hashs[maxn]; int pos; ULL ha[maxn]; int cmp(const int &a, const int &b)///cmp注意 { return ha[a] < ha[b] || (ha[a] == ha[b] && a < b); } int possible(int L) { for (int i = 0; i < n - L + 1; i++) { rank[i] = i; /// ha[i] = hashs[i] - hashs[i + L] * xp[L]; } sort(rank, rank + n - L + 1, cmp); int x; pos = -1; for (int i = 0; i < n - L + 1; i++) { if (i == 0 || ha[rank[i]] != ha[rank[i - 1]]) x = 0; if (++x >= m) pos = max(pos, rank[i]); } return pos >= 0; } int main() { /// xp[0] = 1; for (int i = 1; i < maxn; i++) xp[i] = xp[i - 1] * SEED; while (cin >> m && m) { RS(s); n = strlen(s); /// hashs[n] = 0; for (int i = n - 1; i >= 0; i--) hashs[i] = hashs[i + 1] * SEED + s[i]; if (!possible(1)) puts("none"); else { int L = 1, R = n; while (L <= R) { int M = (L + R) >> 1; if (possible(M)) L = M + 1; else R = M - 1; } possible(R); printf("%d %d\n", R, pos); } } return 0; }