CSL 的密码

解题思路

后缀数组。对于每一个后缀\(k\)都有\(n - k + 1\)个前缀，把所有不和前一个(排序后的)公共且长度大于\(m\)的前缀个数加起来。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 100005;

int x[N], y[N], c[N], sa[N];

char s[N];

int n, m;

void get_SA()

{

    for(int i = 1; i <= m; i ++) c[i] = 0;

    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++;

    for(int i = 1; i <= m; i ++) c[i] += c[i - 1];

    for(int i = n; i >= 1; i --) sa[c[x[i]] --] = i;

    for(int k = 1; k <= n; k <<= 1){

        int num = 0;

        for(int i = n - k + 1; i <= n; i ++) y[++num] = i;

        for(int i = 1; i <= n; i ++) if(sa[i] > k) y[++num] = sa[i] - k;

        for(int i = 1; i <= m; i ++) c[i] = 0;

        for(int i = 1; i <= n; i ++) c[x[i]] ++;

        for(int i = 1; i <= m; i ++) c[i] += c[i - 1];

        for(int i = n; i >= 1; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;

        num = 1;

        swap(x, y);

        x[sa[1]] = num;

        for(int i = 2; i <= n; i ++){

            if(sa[i] + k <= n && sa[i - 1] + k <= n)

                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])? num: ++num;

            else

                x[sa[i]] = ++num;

        }

        if(num == n)

            break;

        m = num;

    }

}

int height[N], rk[N];

void get_h()

{

    int k = 0;

    for(int i = 1; i <= n; i ++) rk[sa[i]] = i;

    for(int i = 1; i <= n; i ++){

        if(rk[i] == 1) continue;

        if(k) --k;

        int j = sa[rk[i] - 1];

        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;

        height[rk[i]] = k;

    }

}

int main()

{

    int len;

    scanf("%d%d", &n, &len);

    m = 'z';

    scanf("%s", s + 1);

    get_SA();

    get_h();

    ll ans = 0;

    for(int i = 1; i <= n; i ++){

        if(sa[i] > n - len + 1) continue;

        int num = n - sa[i] + 1 - len + 1;

        ans += num - max(0, height[i] - len + 1);

    }

    printf("%lld\n", ans);

    return 0;

}

巴特西

CSL 的密码(后缀数组)

CSL 的密码

解题思路

代码如下

最新文章

热门文章