如题= =自用模板

后缀自动机 空间O(n) 时间O(n) 说是这么说 但对于一个1e5的字符串 需要开2×1e5×(字符集大小) 也就是说一般要开2×1e5×26的空间 Java会被卡32768K的内存= = 再说说后缀自动机的几个性质 每个点代表的是一个状态 就是一个状态中所有子串enpos集相同 且每一个点能有多个前驱 但只有一个fa指针 fa指针代表的子串集出现的次数必然大于这个点的代表的子串集出现次数 且fa是这个点的后缀 然后还有每个点子串集合的大小用 st[i].len-st[st[i].fa].len 得到 下面是求原串所有子串中出现正好k次的子串的个数
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
134
135
136
137
138
139
140
141
142
143
144
import java.io.*;  
import java.util.*;  
public class Main {  
static int[]dp=new int[(int) 2e5];  
    public static void main(String[] args){  
        FastScanner sc=new FastScanner();  
        PrintWriter pw=new PrintWriter(System.out);  
        StringBuilder sb=new StringBuilder();  
        int t=sc.nextInt();  
        Sam sam=new Sam();  
        for(int o=1;o<=t;o++){  
            int k=sc.nextInt();  
            String s=sc.next();  
            int lens=s.length();  
            sam.init();  
            for(int i=0;i<lens;i++){  
                sam.add(s.charAt(i)-'a');  
            }  
            long sum=0;  
            for(int i = 0; i <= sam.tots; ++i) dp[i] = 0;  
            sam.topsort(lens);  
            int p=sam.root;  
            for(int i=0;i<lens;i++){  
                //p=sam.st[p].map.get(s.charAt(i)-'a');  
                p = sam.st[p].son[s.charAt(i)-'a'];  
                dp[p]++;  
            }  
            for(int i = sam.tots; i >= 1; --i){    
                p = sam.r[i];    
                if(sam.st[p].fa != -1) dp[sam.st[p].fa] += dp[p];    
            }    
            long ans1 = 0;  
            long ans2 = 0;    
            for(int i = 1; i <= sam.tots; ++i){    
                if(dp[i] >= k){  
                    ans1 += sam.st[i].len-sam.st[sam.st[i].fa].len;    
                }  
            }  
            for(int i = 1; i <= sam.tots; ++i){    
                if(dp[i] >= k+1) {  
                    ans2 += sam.st[i].len-sam.st[sam.st[i].fa].len;   
                }  
            }  
            /*for(int i=1;i<=sam.last;i++){ 
                if(sam.st[i].cnt==k){ 
                    sum+=sam.st[i].len-sam.st[sam.st[i].fa].len; 
                } 
            }*/  
            pw.println(ans1-ans2);  
            pw.flush();  
        }  
  
    }  
  
}  
class Sam{  
    static int maxn=100005; //字符串长度  
    static int maxm=26;//字符种类  
    Node[]st;  
    int root,last;  
    int tots;  
    static int[]w=new int[maxn];  
    static int[]r=new int[maxn*2];  
    Sam(){  
        st=new Node[2*maxn];  
        for(int i=0;i<2*maxn;i++){  
            st[i]=new Node();  
            st[i].son=new int[maxm];  
            //st[i].map=new HashMap<Integer,Integer>();  
        }  
    }  
     
    void init(){  
        tots=0;  
        root=last=0;  
        st[tots].init(0);  
        /* 若关于不同的字符串多次建立后缀自动机，就需要执行这些代码：  
            for (int i=0; i<maxn*2; ++i) { 
                Arrays.fill(st[i].son,-1); 
            } 
        */    
    }  
      
    void add(int c){  
        int p = last;    
        int np = ++tots;    
        st[tots].init(st[p].len+1);  
        int q, nq;    
        while(p != -1 && st[p].son[c] == -1){  /*st[p].map.get(c)==null*/  
            st[p].son[c] = np;    
            //st[p].map.put(c, np);    
            p = st[p].fa;    
        }    
        if(p == -1){  
            st[np].fa = root;    
        }else{    
            q = st[p].son[c];   
            //q = st[p].map.get(c);   
            if ((st[p].len+1) == st[q].len){  
                st[np].fa=q;    
            }else{    
                nq = ++tots;    
                st[nq].init(0);    
                st[nq].fa = st[q].fa;   
                for(int i=0;i<26;i++){  
                    st[nq].son[i]=st[q].son[i];  
                }  
                st[nq].len = st[p].len+1;    
                st[q].fa = nq;    
                st[np].fa = nq;    
                while(p!=-1&&st[p].son[c]==q){    
                    st[p].son[c] = nq;   
                    //st[p].map.put(c, np);    
                    p = st[p].fa;    
                }    
            }    
        }    
        last = np;  
        /*for(int i=last;i!=root;i=st[i].fa){ 
            st[i].cnt++; 
        } 
        n^2求每个状态出现的次数 每加一个点它的所有fa必定出现一次 总次数是st[i].cnt*(st[i].len-st[st[i].pre].len) 
        */  
    }  
      
    void topsort(int stringlen){    
        for(int i = 0; i <= stringlen; ++i) w[i] = 0;    
        for(int i = 1; i <= tots; ++i) w[st[i].len]++;    
        for(int i = 1; i <= stringlen; ++i) w[i] += w[i-1];    
        for(int i = tots; i >= 1; --i) r[w[st[i].len]--] = i;    
        r[0] = 0;    
    }   
    static class Node{  
        int len,fa;  
        int[]son;  
        //HashMap<Integer,Integer>map;  
        void init(int lenp){  
            len=lenp;  
            fa=-1;  
            Arrays.fill(son,-1);  
            //map.clear();  
        }  
    }  
}