如题= =自用模板

后缀数组 目前整理了nlogn的板子 sa[i]里的值代表排名为i的后缀的起始位置 rank[i]里的值代表起始位置为i的后缀排第几 height从height[2]开始有效 表示sa[i]和sa[i-1]这两个后缀的最长公共前缀 rmq用于求一个串中任意两个后缀的最长公共前缀 O(nlogn) 还有一个重要的性质就是一个字符串所有子串的最长公共前缀取值都在h[i]中 所以在求两个串的最长公共子串时 可以在两个串中加一个特殊字符 然后枚举h[i]使得s[i]和s[i]-1落在特殊字符的两端
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.io.*;  
import java.util.*;  
public class Main {  
  
    public static void main(String[] args) {  
        FastScanner sc=new FastScanner();  
        PrintWriter pw=new PrintWriter(System.out);  
        SA sa=new SA();  
        while(sc.hasNext()){  
            String s=sc.next();  
            sa.getSA(s);  //获得SA数组
            sa.getHeight();  //利用sa算rank并计算height
            int n=sc.nextInt();  
            long left=0;  
            long right=0;  
            int prel=sc.nextInt();  
            int prer=sc.nextInt();  
            left+=prer-prel+1;  
            right+=3+prer-prel;  
            sa.rmqinit(); //非常重要的初始化  
            for(int o=2;o<=n;o++){  
                int l=sc.nextInt();  
                int r=sc.nextInt();  
                left+=r-l+1;  
                int k=Math.min(sa.queryLCP(prel, l), Math.min(prer-prel, r-l));  
                right+=r-l+2+String.valueOf(k).length()-k;  
                prel=l;  
                prer=r;  
            }  
            pw.println(left+" "+right);  
            pw.flush();  
        }  
  
    }  
  
}  
class SA{  
    /*【倍增算法O(nlgn)】待排序的字符串放在r 数组中，从r[0]到r[n-1]，长度为n，且最大值小于m  
      使用倍增算法前，需要保证r数组的值均大于0。然后要在原字符串后添加一个0号字符  
      所以，若原串的长度为n，则实际要进行后缀数组构建的r数组的长度应该为n+1.所以调用da函数时，对应的n应为n+1.  
      【使用说明】：字符串从0下标开始，算法最后要加上一个0，sa的值是0~n-1(下标为1~n)，rank的值是1~n(下标是0~n-1)，height下标从0开始，但是  
      height[0]=0,height[1]=0,height[2]才表示与前一个的最长公共前缀。  
      height[i]排名为i的后缀与排名i-1的后缀的最长公共前缀 相当于height下标为2~n 
    */    
    int maxn=100050;  
    int[]sa,wa,wb,ws,wv;  
    int[]rank;  
    int[]height;  
    int[]r;  
    int[][]dp;  
    int n;  
    int m;  
    SA(){  
        sa=new int[maxn];  
        wa=new int[maxn];  
        wb=new int[maxn];  
        ws=new int[maxn];  
        wv=new int[maxn];  
        height=new int[maxn];  
        rank=new int[maxn];  
        r=new int[maxn];  
        dp=new int[maxn][20];  
    }  
      
    boolean cmp(int[]f,int x,int y,int w){  
        return f[x] == f[y] && f[x + w] == f[y + w];  
    }  
      
    void getSA(String s){  
        n=s.length();  
        for(int i=0;i<s.length();i++){  
            r[i]=s.charAt(i);  
        }  
        r[n]=0;  
        da(r,sa,s.length()+1,128);  
    }     
      
    void getHeight(){  
        calheight(r,sa,n);  
    }  
      
    void da(int[] r, int sa[], int n, int m){  
        int i, j, p;  
        int[]x = wa;  
        int[]y = wb;  
        int[]temp;  
        for (i = 0; i < m; ++i) ws[i] = 0;  
        for (i = 0; i < n; ++i) ws[x[i]=r[i]]++;  
        for (i = 1; i < m; ++i) ws[i] += ws[i-1];  
        for (i = n-1; i >= 0; --i) sa[--ws[x[i]]] = i;  
        for (j = 1, p = 1; p < n; j *= 2, m = p){  
            for (p = 0, 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 < n; ++i) wv[i] = x[y[i]];  
            for (i = 0; i < m; ++i) ws[i] = 0;  
            for (i = 0; i < n; ++i) ws[wv[i]]++;  
            for (i = 1; i < m; ++i) ws[i] += ws[i-1];  
            for (i = n-1; i >= 0; --i) sa[--ws[wv[i]]] = y[i];  
            for (temp=x,x=y,y=temp, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)  
                x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? (p-1) : p++;  
        }  
    }  
      
    void calheight(int[] r, int sa[], int n){  
        int i, j, k = 0;  
        for (i = 1; i <= n; ++i) rank[sa[i]] = i;  
        for (i = 0; i < n; height[rank[i++]] = k){  
            if(k>0)k--;  
            for (j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);  
        }       
    }  
    void rmqinit(){  
        for(int i=1;i<=n;i++)dp[i][0]=height[i];    
        for(int j=1;(1<<j)<=n;++j)    
            for(int i=1;i+(1<<j)-1<=n;++i)    
                dp[i][j]=Math.min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);    
    }  
    int queryLCP(int i,int j){ //from 0~n-1 返回i~n-1 和j~n-1两个后缀的最长公告前缀   
        if(i==j)    
            return n-i;    
        if(rank[i]<rank[j])    
            return q(rank[i]+1,rank[j]);    
        else    
            return q(rank[j]+1,rank[i]);    
          
    }  
    int q(int l,int r){    
        int k=(int) (Math.log(r-l+1)/Math.log(2));    
        /*int k=0;   
        while((1<<(1+k))<=r-l+1) k++;*/    
        return Math.min(dp[l][k],dp[r-(1<<k)+1][k]);    
    }    
}