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
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int MM=200005;
int head[200005],nt[200005*26],to[200005*26];
class SAM {
public:
    vector<int> maxlen,minlen,slink;
    int trans[MM][26];
    int n,len,st;
    int NUM_ST;
    int MASK_SZ;
    void init(string &s) {
        NUM_ST = 26;
        len = s.length();
        n = 0;
        int MAXM = len*2+10;
        maxlen.assign(MAXM,0);
        minlen.assign(MAXM,0);
        slink.assign(MAXM,0);
        st = new_state(0,0,-1,-1);
        for(int i = 0; i < len; i++) {
            st = add_char(s[i],st);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX