POJ 1743 Musical Theme（后缀数组）

题意：有n个数值，算出相邻两个值的差值，此时有n-1个值的序列，把这序列当做字符串的话，求最长重复子串，且这两个子串不能重叠。

分析：后缀数组解决。先二分答案，把题目变成判定性问题：判断是否存在两个长度为k 的子串是相同的，且不重叠。

只能说后缀数组很强大

PS：刚好是男人八题之一..........8分之1男人了.......

#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= k) return true;  
    }  
    return false;  
}  
  
int main() {  
    int n,t,tt;  
    while(scanf("%d",&n) && n) {  
        scanf("%d",&tt);  
        -- n;  
        for(int i=0; i> 1;  
            if(judge(mid,n)) {  
                ans = mid;  
                l = mid + 1;  
            } else {  
                r = mid - 1;  
            }  
        }  
        ans ++;  
        if(ans >= 5) cout << ans << endl;  
        else cout << 0 << 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= k) return true;
    }
    return false;
}

int main() {
    int n,t,tt;
    while(scanf("%d",&n) && n) {
        scanf("%d",&tt);
        -- n;
        for(int i=0; i> 1;
            if(judge(mid,n)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans ++;
        if(ans >= 5) cout << ans << endl;
        else cout << 0 << endl;
    }
    return 0;
}