跳转至

字符串¶

KMP¶

for(int i = 2, j = 0; i <= n; ++i){
    while(s[i] != s[j + 1]) j = next[j];
    if(s[i] == s[j + 1]) ++j;
    next[i] = j;
}

字符串哈希¶

struct hash_engine{
    ull key[maxn], basep[maxn], base;
    void init(const char *s, int n){
        base = 319ull, basep[0] = 1ull;
        for(int i = 1; i <= n; ++i){
            key[i] = key[i - 1] * base + s[i];
            basep[i] = basep[i - 1] * base;
        }
    }
    ull operator()(int l, int r)const{
        if(l > r)
            return 0ull;
        return key[r] - key[l - 1] * basep[r - l + 1];
    }
}mhash;

后缀数组¶

void build_suffix(char *s, int *sa, int *rk, int n){
    static int m, cnt[maxn], oldsa[maxn], oldrk[maxn << 1]; m = 0;
    for(int i = 1; i <= n; ++i) ++cnt[(int)s[i]], m = std::max<int>(m, s[i]);
    for(int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
    for(int i = n; i >= 1; --i) sa[cnt[(int)s[i]]--] = i;
    for(int i = 1 + (m = 0); i <= n; ++i) rk[sa[i]] = s[sa[i]] == s[sa[i - 1]] ? m : ++m;
    for(int w = 1; m < n; w <<= 1){
        std::fill(cnt, cnt + m + 1, 0), std::copy(rk + 1, rk + n + 1, oldrk + 1);
        for(int i = n - w + 1; i <= n; ++i) oldsa[++cnt[0]] = i;
        for(int i = 1; i <= n; ++i) if(sa[i] > w) oldsa[++cnt[0]] = sa[i] - w;
        for(int i = 1; i <= n; ++i) ++cnt[rk[i]];
        for(int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
        for(int i = n; i >= 1; --i) sa[cnt[rk[oldsa[i]]]--] = oldsa[i];
        for(int i = 1 + (m = 0); i <= n; ++i)
            rk[sa[i]] = oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w] ? m : ++m;
    }
}

Lyndon 分解¶

for(int i = 1; i <= n; ){
    int j = i, k = i;
    while(k + 1 <= n && s[j] <= s[k + 1])
        if(s[j] == s[k + 1]) ++j, ++k;
        else j = i, ++k;
    while(i <= j) i += k - j + 1;
}

AC 自动机¶

Run¶

int find_prev(int a, int b){
    int l = 0, r = std::min(a, b);
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(mhash(a - mid + 1, a) == mhash(b - mid + 1, b))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int find_next(int a, int b){
    int l = 0, r = std::min(n - a + 1, n - b + 1);
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(mhash(a, a + mid - 1) == mhash(b, b + mid - 1))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

void lyndon(int opt, int *Lyn){
    if(opt) s[n + 1] = 'a' - 1;
    else s[n + 1] = 'z' + 1;
    static int st[maxn], top;
    st[0] = n + 1, top = 0;
    for(int i = n; i >= 1; --i){
        while(top){
            int x = find_next(i, st[top]);
            if(opt ? s[i + x] < s[st[top] + x] : s[i + x] > s[st[top] + x])
                --top;
            else
                break;
        }
        Lyn[i] = st[top] - 1, st[++top] = i;
    }
}

std::vector<std::pair<std::pair<int, int>, int> > runs(const char *s){
    std::vector<std::pair<std::pair<int, int>, int> > ans;
    static int int lyn[maxn];

    n = std::strlen(s + 1), mhash.init(s, n);

    for(int opt = 0; opt < 2; ++opt){
        lyndon(opt, lyn);
        for(int i = 1; i <= n; ++i){
            int l = i, r = lyn[i], p = r - l + 1;
            std::pair<int, int> mr(l - find_prev(l - 1, r), r + find_next(l, r + 1));
            if(p * 2 <= mr.second - mr.first + 1)
                ans.push_back(std::make_pair(mr, p));
        }
    }

    std::sort(ans.begin(), ans.end());
    ans.resize(std::unique(ans.begin(), ans.end()) - ans.begin());

    return ans;
}

评论