Skip to content

Instantly share code, notes, and snippets.

@ShikChen
Created March 25, 2018 11:11
Show Gist options
  • Save ShikChen/b98a85f2c44ae1352acff1d7ebebd854 to your computer and use it in GitHub Desktop.
Save ShikChen/b98a85f2c44ae1352acff1d7ebebd854 to your computer and use it in GitHub Desktop.
struct SAM {
struct nd { int l, p; array<int, 26> e; };
vector<nd> v;
SAM() : v(2, nd{0, 0, {0}}) {}
void push(int c) {
int wh = v.size(), st = wh - 1, it = st;
while (it && !v[it].e[c]) it = v[it].p;
if (it && v[v[it].e[c]].l != v[it].l + 1) {
int cp = wh++, ob = v[it].e[c];
v.push_back(nd{v[it].l + 1, v[ob].p, v[ob].e});
for (v[ob].p = cp; it && v[it].e[c] == ob; it = v[it].p) v[it].e[c] = cp;
}
for (it = st; it && !v[it].e[c]; it = v[it].p) v[it].e[c] = wh;
v.push_back(nd{v[st].l + 1, it ? v[it].e[c] : 1, v[0].e});
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment