首页 > 代码库 > SPOJ 8222 NSUBSTR Substrings
SPOJ 8222 NSUBSTR Substrings
SAM的简单应用....
由SAM可知从root到达的每个节点所经过的路径都对着应原串的一个子串,每个节点能到几次接收态就等于这个子串出现了几次。从最后一个节点往上走,就可以用DP更新出每个子串出现了多少次。
出现了5次的子串一定也出现了4,3,2,1次。。。所以最后再用长度长的给长度小的更新一下。。。。
Substrings
Time Limit: 1000MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
[Submit] [Go Back] [Status]
Description
You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa‘ F(3) will be 2 because there is a string ‘aba‘ that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|.
Input
String S consists of at most 250000 lowercase latin letters.
Output
Output |S| lines. On the i-th line output F(i).
Example
Input: ababa Output: 3 2 2 1 1
Source
Immagination
[Submit] [Go Back] [Status]
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=600000; struct SAM_Node { SAM_Node *fa,*next[26]; int len,id,pos; SAM_Node(){} SAM_Node(int _len) { len=_len; fa=0; memset(next,0,sizeof(next)); } }; SAM_Node SAM_node[maxn*2],*SAM_root,*SAM_last; int SAM_size; SAM_Node *newSAM_Node(int len) { SAM_node[SAM_size]=SAM_Node(len); SAM_node[SAM_size].id=SAM_size; return &SAM_node[SAM_size++]; } SAM_Node *newSAM_Node(SAM_Node *p) { SAM_node[SAM_size]=*p; SAM_node[SAM_size].id=SAM_size; return &SAM_node[SAM_size++]; } void SAM_init() { SAM_size=0; SAM_root=SAM_last=newSAM_Node(0); SAM_node[0].pos=0; } void SAM_add(int x,int len) { SAM_Node *p=SAM_last,*np=newSAM_Node(p->len+1); np->pos=len; SAM_last=np; for(;p&&!p->next[x];p=p->fa) p->next[x]=np; if(!p) { np->fa=SAM_root; return ; } SAM_Node *q=p->next[x]; if(q->len==p->len+1) { np->fa=q; return ; } SAM_Node *nq=newSAM_Node(q); nq->len=p->len+1; q->fa=nq; np->fa=nq; for(;p&&p->next[x]==q;p=p->fa) p->next[x]=nq; } char str[maxn]; bool vis[maxn]; int r[maxn],dp[maxn]; int Find(SAM_Node *p) { if(vis[p->id]==true) return r[p->id]; vis[p->id]=true; r[p->id]=0; for(int i=0;i<26;i++) { if(p->next[i]) r[p->id]+=Find(p->next[i]); } return r[p->id]; } void get_count() { memset(r,0,sizeof(r)); memset(vis,0,sizeof(vis)); SAM_Node *p=SAM_last; vis[p->id]=true; for(;p;p=p->fa) { Find(p); r[p->id]++; } } int main() { while(scanf("%s",str)!=EOF) { int n=strlen(str); SAM_init(); for(int i=0;i<n;i++) SAM_add(str[i]-'a',i+1); get_count(); memset(dp,0,sizeof(dp)); for(int i=0;i<SAM_size;i++) { dp[SAM_node[i].len]=max(dp[SAM_node[i].len],r[SAM_node[i].id]); } for(int i=n-1;i>=1;i--) { dp[i]=max(dp[i],dp[i+1]); } for(int i=1;i<=n;i++) { printf("%d\n",dp[i]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。