Factor Oracle

fo.cpp

#include<algorithm>
#include<vector>
#define For(i, n) for(i = 0; i < n; i++)
#define Forr(i, l, n) for(i = l; i < n; i++)
typedef long long LL;
using namespace std;

const int N = 200005;
const int E = 26;

class FactorOracle{
        int trans[N][E]; //transition
        int _LCS(int p1, int p2){
            if(p2 == sp[p1]) return lrs[p1];
            while(sp[p2] != sp[p1]) p2 = sp[p2];
            return min(lrs[p1], lrs[p2]);
        }
    public:
        int lrs[N]; // lengthRepeatedSuffix
        // suffix link; 
        // sp[i] = j , means the first ocurrence of the repeated suffix of state i ends in j

        int sp[N];
        int n;
        void reset(){
            n = 0;
            sp[0] = -1;
            lrs[0] = 0;
            memset(trans, -1, sizeof trans);
        }
        void add_sep(){
            n++;
            sp[n] = lrs[n] = 0;
        }
        void add_letter(int cc){
            // cc: char code
            int j, p1;
            trans[n][cc] = n + 1;
            j = sp[p1=n];
            ++n;
            while(j != -1 and trans[j][cc] == -1){
                trans[j][cc] = n;
                j = sp[p1=j];
            }
            sp[n] = (j == -1 ? 0 : trans[j][cc]);
            lrs[n] = (sp[n] == 0 ? 0 : _LCS(p1, sp[n]-1) + 1);
        };
};

FactorOracle fo;

int main(){
    string s;
    int i;
    int cc;
    cin >> s;
    fo.reset();
    For(i, s.size()){
        cc = s[i] - 'a';
        if(cc < E and cc >= 0)
            fo.add_letter(cc);
        else
            fo.add_sep();
        printf("%2d: %c lrs:%2d sp:%2d\n", i+1, s[i], fo.lrs[i+1], fo.sp[i+1]);
    }
}