CFGYM103176C-camelCaseCounting

Mean

给定一个长为\(n\)的字符串，存在大小写字母，问本质不同的小写字母开头的串的数目。\(n<=1e6\)。

Sol

由于题目只给了\(1S\)，可以大胆猜测是个\(O(n)\)相关的题。

考虑建出\(SAM\)，每个状态中维护最大的\(endpos\)位置信息\(f[u]\).

那么每个状态对答案的贡献取决于\([f[i]-node[i].len,f[i]-node[node[i].fa].len]\)中有多少个小写字母。

前缀和预处理一下，最后直接计数即可。

复杂度\(O(n)\).

比较奇怪的是\(SAM\)跑得没\(SA\)慢好多，先写\(SAM\)的做法吧，回头更\(SA\)的做法。

Code(SAM)

#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int tot = 1, last = 1;

struct Node
{
    int len, fa;
    int ch[53];
}node[N*2];
char str[N];
ll f[N*2], ans;
int h[N*2], e[N*3], ne[N*3], idx;

int getch(char x){
    if(x>='a'&&x<='z')return x-'a';
    else return 26+x-'A';
}
void extend(int c,int id)
{
    int p = last, np = last = ++ tot;
    f[tot] = id;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        dfs(e[i]);
        f[u] =max(f[u], f[e[i]]);
    }
}

int sum[N];

int main()
{
    scanf("%s", str+1);
    int lens=strlen(str+1);
    for (int i = 1; str[i]; i ++ ) extend(getch(str[i]),i);
    memset(h,-1,sizeof(h));
    for(int i=2;i<=tot;++i){
        add(node[i].fa,i);
    }
    dfs(1);
    for(int i = 1;i<=lens;++i){
        if(str[i]>='a'&&str[i]<='z')sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }

    for(int i=2;i<=tot;++i){
        int l = f[i]-node[i].len+1;
        int r = f[i]-node[node[i].fa].len;
        ans = ans+sum[r]-sum[l-1];
    }
    printf("%lld\n",ans);
    return 0;
}

Code(SA)

wating.