COGS 1709 [SPOJ705]不同的子串

【题目描述】
给定一个字符串,计算其不同的子串个数。

【输入格式】
一行一个仅包含大写字母的字符串,长度<=50000

【输出格式】
一行一个正整数,即不同的子串个数。

【样例输入】
ABABA
【样例输出】
9
【来源】
SPOJ 705 New Distinct Substrings

神奇的自动机。。。跑起来似乎有些慢。。。。COGS榜上全是后缀数组。。。。。。滚去睡。。。。明天再去看看hashit……

#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXNODE 100100
char s[50100];
struct samnode {
    samnode *par, *ch[26];
    int val;
    samnode() { 
        par = 0; memset(ch, 0, sizeof(ch));
        val = 0;
    }
} node[MAXNODE], *root, *last;
int size = 0;
inline void init() {
    last = root = &node[0];
}
inline void add(int c) {
    samnode *p = last;
    samnode *np = &node[++size]; np->val = p->val + 1;
    while (p && !p->ch[c])
        p->ch[c] = np, p = p->par;
    if (!p) np->par = root;
    else {
        samnode *q = p->ch[c];
        if (q->val == p->val + 1)
            np->par = q;
        else {
            samnode *nq = &node[++size]; nq->val = p->val + 1;
            memcpy(nq->ch, q->ch, sizeof(q->ch));
            nq->par = q->par;
            q->par = np->par = nq;
            while (p && p->ch[c] == q)
                p->ch[c] = nq, p = p->par;
        }
    } last = np;
}
int main(){
	freopen("subst1.in" ,"r",stdin ) ;
	freopen("subst1.out","w",stdout) ;
	init();
	scanf("%s",s);
	int n=strlen(s),ans=0;
	for(int i=0;i<n;i++) add(s[i]-'A');
	for(int i=1;i<=size;i++) ans+=node[i].val-node[i].par->val;
	printf("%d\n",ans);
	return 0;
}

 

此条目发表在COGS, SAM, SPOJ分类目录。将固定链接加入收藏夹。