脚本宝典收集整理的这篇文章主要介绍了CFGYM103176C-camelCaseCounting (SAM/SA)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

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("%lldn",ans);
    return 0;
}

Code(SA)

wating.

脚本宝典总结

以上是脚本宝典为你收集整理的CFGYM103176C-camelCaseCounting (SAM/SA)全部内容，希望文章能够帮你解决CFGYM103176C-camelCaseCounting (SAM/SA)所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。