POJ 3261 Milk Patterns（后缀数组+二分答案+离散化）

题意：给定一个字符串，求至少出现k 次的最长重复子串，这k 个子串可以重叠。

分析：经典的后缀数组求解题：先二分答案，然后将后缀分成若干组。这里要判断的是有没有一个组的符合要求的后缀个数（height[i] >= mid）不小于k。如果有，那么存在
k 个相同的子串满足条件，否则不存在

#include    
#include    
#include    
#include    
using namespace std;  
#define N 22222   
#define M 1111111   
#define INF 0x7FFFFFFF   
/****后缀数组模版****/  
#define F(x)((x)/3+((x)%3==1 0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置   
#define G(x)((x)=0; i--)  
        b[--WS[wv[i]]]=a[i];  
    return;  
}  
  
//注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n   
void dc3(int *r,int *sa,int n,int m) { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa   
    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= mid) {  
            cnt ++;  
        } else cnt = 1;  
        if(cnt >= k) return true;  
    }  
    return false;  
}  
  
int main() {  
    int n,k;  
    cin >> n >> k;  
    for(int i=0; i> 1;  
        if(judge(mid,n,k)) {  
            ans = mid;  
            l = mid + 1;  
        } else {  
            r = mid - 1;  
        }  
    }  
    cout << ans << endl;  
    return 0;  
}  

#include 
#include 
#include 
#include 
using namespace std;
#define N 22222
#define M 1111111
#define INF 0x7FFFFFFF
/****后缀数组模版****/
#define F(x)((x)/3+((x)%3==1 0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置
#define G(x)((x)=0; i--)
        b[--WS[wv[i]]]=a[i];
    return;
}

//注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
void dc3(int *r,int *sa,int n,int m) { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    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= mid) {
            cnt ++;
        } else cnt = 1;
        if(cnt >= k) return true;
    }
    return false;
}

int main() {
    int n,k;
    cin >> n >> k;
    for(int i=0; i> 1;
        if(judge(mid,n,k)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

因为m太大，而n只有2w，简单的离散化之后，基数排序效率提高，总效率也提高了

#include    
#include    
#include    
#include    
using namespace std;  
#define N 22222   
#define INF 0x7FFFFFFF   
/****后缀数组模版****/  
#define F(x)((x)/3+((x)%3==1 0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置   
#define G(x)((x)=0; i--)  
        b[--WS[wv[i]]]=a[i];  
    return;  
}  
  
//注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n   
void dc3(int *r,int *sa,int n,int m) { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa   
    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= mid) {  
            cnt ++;  
        } else cnt = 1;  
        if(cnt >= k) return true;  
    }  
    return false;  
}  
int xx[N],x[N];  
int search(int v,int m) {  
    int l = 0,r = m-1;  
    while(l <= r) {  
        int mid = (l + r) /2;  
        if(x[mid] == v)  
            return mid;  
        if(v < x[mid])  
            r = mid-1;  
        else  
            l = mid+1;  
    }  
    return -1;  
}  
int main() {  
    int n,k;  
    cin >> n >> k;  
    for(int i=0; i> 1;  
        if(judge(mid,n,k)) {  
            ans = mid;  
            l = mid + 1;  
        } else {  
            r = mid - 1;  
        }  
    }  
    cout << ans << endl;  
    return 0;  
}  

#include 
#include 
#include 
#include 
using namespace std;
#define N 22222
#define INF 0x7FFFFFFF
/****后缀数组模版****/
#define F(x)((x)/3+((x)%3==1 0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置
#define G(x)((x)=0; i--)
        b[--WS[wv[i]]]=a[i];
    return;
}

//注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
void dc3(int *r,int *sa,int n,int m) { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    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= mid) {
            cnt ++;
        } else cnt = 1;
        if(cnt >= k) return true;
    }
    return false;
}
int xx[N],x[N];
int search(int v,int m) {
    int l = 0,r = m-1;
    while(l <= r) {
        int mid = (l + r) /2;
        if(x[mid] == v)
            return mid;
        if(v < x[mid])
            r = mid-1;
        else
            l = mid+1;
    }
    return -1;
}
int main() {
    int n,k;
    cin >> n >> k;
    for(int i=0; i> 1;
        if(judge(mid,n,k)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}