Boring counting
题目描述
035 now faced a tough problem,his english teacher gives him a string,which consists with n lower case letter,he must figure out how many substrings appear at least twice,moreover,such apearances can not overlap each other.Take aaaa as an example.”a” apears four times,”aa” apears two times without overlaping.however,aaa can’t apear more than one time without overlaping.since we can get “aaa” from [0-2](The position of string begins with 0) and [1-3]. But the interval [0-2] and [1-3] overlaps each other.So “aaa” can not take into account.Therefore,the answer is 2(“a”,and “aa”).
输入描述:
输出描述:
输入
输出
2 3 3#include
#include
#define max 11000
int wa[max],wb[max],wv[max],ws[max];
int rank[max],height[max];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)
{int i,j,p,*x=wa,*y=wb,*t;for(i=0; i=0; i--) sa[--ws[x[i]]]=i;for(p=1,j=1; p=j) y[p++]=sa[i]-j;for(i=0; i=0; i--) sa[--ws[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i=i){int tem=sa[j-1]>sa[j]?sa[j]:sa[j-1];mint=mint>tem?tem:mint;tem=sa[j-1]>sa[j]?sa[j-1]:sa[j];maxt=maxt>tem?maxt:tem; }else{if(mint+i<=maxt)ans++;mint=1001,maxt=-1;}}if(mint+i<=maxt)ans++;}printf("%d\n",ans);}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！