loading改版人：小Angel，初稿：2016-7-26，当前2016-7-28，版本1.0
void insert(char buf[]) {
int len = strlen(buf); int now = root;
for(int i =0; i < len; i++) {
if(next[now][buf[i]-'a']==-1)
next[now][buf[i]-'a']= newnode(); now = next[now][buf[i]-'a']; }
end[now]++; }
void build() {
queue
fail[root]= root; for(int i =0; i <26; i++) if(next[root][i]==-1)
next[root][i]= root; else {
fail[next[root][i]]= root; Q.push(next[root][i]); }
while(!Q.empty()) {
int now = Q.front(); Q.pop();
for(int i =0; i <26; i++) if(next[now][i]==-1)
next[now][i]= next[fail[now]][i]; else {
fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } }
int query(char buf[]) {
int len = strlen(buf); int now = root; int res =0;
for(int i =0; i < len; i++) {
now = next[now][buf[i]-'a']; int temp = now;
while( temp != root ) {
res += end[temp]; end[temp]=0;
temp = fail[temp]; } }
return res; }
void debug() {
for(int i =0; i < L; i++) {
printf(\[\,i,fail[i],end[i]);
for(int j =0; j <26; j++)
printf(\,next[i][j]); printf(\); } } };
char buf[1000010]; Trie ac; int main() {
int T; int n;
scanf(\,&T); while( T--) {
scanf(\,&n); ac.init();
for(int i =0; i < n; i++)
{
scanf(\,buf); ac.insert(buf); }
ac.build();
scanf(\,buf);
printf(\,ac.query(buf)); }
return0; }
5、后缀数组 5.1 DA算法 /*
*suffix array
*倍增算法 O(n*logn)
*待排序数组长度为n,放在0~n-1中，在最后面补一个0
*da(str ,n+1,sa,rank,height, , );//注意是n+1; *例如： *n = 8;
*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0
*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值 *sa[]
= { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值 * */
constint MAXN=20010; int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0 //函数结束以后结果放在sa数组中
bool cmp(int*r,int a,int b,int l) {
return r[a]== r[b]&& r[a+l]== r[b+l]; } void da(int str[],int sa[],int rank[],int height[],int n,intm) {
n++;
int i, j, p,*x = t1,*y = t2;
//第一轮基数排序，如果s的最大值很大，可改为快速排序 for(i =0; i < m; i++)c[i]=0;
for(i =0; i < n; i++)c[x[i]= str[i]]++; for(i =1; i < m; i++)c[i]+= c[i-1];
for(i = n-1; i >=0; i--)sa[--c[x[i]]]= i; for(j =1; j <= n; j <<=1) {
p =0;
//直接利用sa数组排序第二关键字
for(i = n-j; i < n; i++)y[p++]= i;//后面的j个数第二关键字为空的最小
for(i =0; i < n; i++)if(sa[i]>= j)y[p++]= sa[i]- j; //这样数组y保存的就是按照第二关键字排序的结果 //基数排序第一关键字
for(i =0; i < m; i++)c[i]=0;
for(i =0; i < n; i++)c[x[y[i]]]++; for(i =1; i < m; i++)c[i]+= c[i-1];
for(i = n-1; i >=0; i--)sa[--c[x[y[i]]]]= y[i]; //根据sa和x数组计算新的x数组 swap(x,y); p =1;
x[sa[0]]=0; for(i =1; i < n; i++)
x[sa[i]]= cmp(y,sa[i-1],sa[i],j)?p-1:p++; if(p >= n)break;
m = p;//下次基数排序的最大值 }
int k =0; n--;
for(i =0; i <= n; i++)rank[sa[i]]= i; for(i =0; i < n; i++) {
if(k)k--;
j = sa[rank[i]-1];
5
改版人：小Angel，初稿：2016-7-26，当前2016-7-28，版本1.0
while(str[i+k]== str[j+k])k++; height[rank[i]]= k; } }
int rank[MAXN],height[MAXN]; int RMQ[MAXN]; int mm[MAXN];
int best[20][MAXN]; void initRMQ(int n) {
mm[0]=-1;
for(int i=1; i<=n; i++)
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; for(int i=1; i<=n; i++)best[0][i]=i; for(int i=1; i<=mm[n]; i++)
for(int j=1; j+(1< int a=best[i-1][j]; int b=best[i-1][j+(1<<(i-1))]; if(RMQ[a] int askRMQ(int a,int b) { int t; t=mm[b-a+1]; b-=(1< return RMQ[a] int lcp(int a,int b) { a=rank[a]; b=rank[b]; if(a>b)swap(a,b); return height[askRMQ(a+1,b)]; } char str[MAXN]; int r[MAXN]; int sa[MAXN]; int main() { while(scanf(\,str)==1) { int len = strlen(str); int n =2*len +1; for(int i =0; i < len; i++)r[i]= str[i]; for(int i =0; i < len; i++)r[len +1+ i]= str[len -1- i]; r[len]=1; r[n]=0; da(r,sa,rank,height,n,128); for(int i=1; i<=n; i++)RMQ[i]=height[i]; initRMQ(n); int ans=0,st; int tmp; for(int i=0; i tmp=lcp(i,n-i);//偶对称 if(2*tmp>ans) { ans=2*tmp; st=i-tmp; } tmp=lcp(i,n-i-1);//奇数对称 if(2*tmp-1>ans) { ans=2*tmp-1; st=i-tmp+1; } } str[st+ans]=0; printf(\,str+st); } return0; } 5.2 DC3算法 da[]和str[]数组要开大三倍，相关数组也是三倍 /* *后缀数组 * DC3算法，复杂度O(n) *所有的相关数组都要开三倍 */ constint MAXN =2010; #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x) int wa[MAXN*3],wb[MAXN*3],wv[MAXN*3],wss[MAXN*3]; int c0(int*r,int a,int b) { return r[a]== r[b]&& r[a+1]== r[b+1]&& r[a+2]== r[b+2]; } int c12(int k,int*r,int a,int b) { if(k ==2) return r[a]< r[b]||( r[a]== r[b]&& c12(1,r,a+1,b+1)); elsereturn r[a]< r[b]||( r[a]== r[b]&& wv[a+1]< wv[b+1]); } void sort(int*r,int*a,int*b,int n,int m) { int i; for(i =0; i < n; i++)wv[i]= r[a[i]]; for(i =0; i < m; i++)wss[i]=0; for(i =0; i < n; i++)wss[wv[i]]++; for(i =1; i < m; i++)wss[i]+= wss[i-1]; for(i = n-1; i >=0; i--) b[--wss[wv[i]]]= a[i]; } void dc3(int*r,int*sa,int n,int m) { int i, j,*rn = r + n; int*san = sa + n, ta =0, tb =(n+1)/3, tbc =0, p; r[n]= r[n+1]=0; for(i =0; i < n; i++)if(i %3!=0)wa[tbc++]= i; sort(r +2, wa, wb, tbc, m); sort(r +1, wb, wa, tbc, m); sort(r, wa, wb, tbc, m); for(p =1, rn[F(wb[0])]=0, i =1; i < tbc; i++) rn[F(wb[i])]= c0(r, wb[i-1], wb[i])? p -1: p++; if(p < tbc)dc3(rn,san,tbc,p); elsefor(i =0; i < tbc; i++)san[rn[i]]= i; for(i =0; i < tbc; i++)if(san[i]< tb)wb[ta++]= san[i]*3; if(n %3==1)wb[ta++]= n -1; sort(r, wb, wa, ta, m); for(i =0; i < tbc; i++)wv[wb[i]= G(san[i])]= i; for(i =0, j =0, p =0; i < ta && j < tbc; p++) sa[p]= c12(wb[j]%3, r, wa[i], wb[j])? wa[i++]: wb[j++]; for(; i < ta; p++)sa[p]= wa[i++]; for(; j < tbc; p++)sa[p]= wb[j++]; } //str和sa也要三倍 void da(int str[],int sa[],int rank[],int height[],int n,int m) { for(int i = n; i < n*3; i++) str[i]=0; dc3(str, sa, n+1, m); int i,j,k =0; for(i =0; i <= n; i++)rank[sa[i]]= i; for(i =0; i < n; i++) { if(k) k--; j = sa[rank[i]-1]; while(str[i+k]== str[j+k]) k++; height[rank[i]]= k; } } 6、后缀自动机 constint CHAR =26; constint MAXN =250010; struct SAM_Node { SAM_Node *fa,*next[CHAR]; int len; int id,pos; SAM_Node(){} SAM_Node(int _len) { fa =0; 6 改版人：小Angel，初稿：2016-7-26，当前2016-7-28，版本1.0 len = _len; 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; } void SAM_build(char*s) { SAM_init(); int len = strlen(s); for(int i =0; i < len; i++) SAM_add(s[i]-'a',i+1); } //加入串后进行拓扑排序。 char str[MAXN]; int topocnt[MAXN]; SAM_Node *topsam[MAXN*2]; int n = strlen(str); SAM_build(str); memset(topocnt,0,sizeof(topocnt)); for(int i =0; i < SAM_size; i++) topocnt[SAM_node[i].len]++; for(int i =1; i <= n; i++) topocnt[i]+= topocnt[i-1]; for(int i =0; i < SAM_size; i++) topsam[--topocnt[SAM_node[i].len]]=&SAM_node[i]; 7 改版人：小Angel，初稿：2016-7-26，当前2016-7-28，版本1.0 数学 1、素数 1.1素数筛选（判断 *素数筛选，判断小于MAXN的数是不是素数。 * notprime是一张表，为false表示是素数，true表示不是素数 */ constint MAXN=1000010; bool notprime[MAXN];//值为false表示素数，值为true表示非素数 void init() { memset(notprime,false,sizeof(notprime)); notprime[0]=notprime[1]=true; for(int i=2; i if(i>MAXN/i)continue;//防止后面i*i溢出(或者i,j用long long) if(s==1)s=2; for(int j=s;(longlong)j*prime[i]<=R; j++) if((longlong)j*prime[i]>=L) notprime[j*prime[i]-L]=true; } prime2[0]=0; for(int i=0; i<=R-L; i++) if(!notprime[i]) prime2[++prime2[0]]=i+L; } int main() { getPrime(); int L,U; while(scanf(\,&L,&U)==2) { getPrime2(L,U); //直接从i*i开始就可以，小于i倍的已经筛选过了,注意是j+=i for(int j=i*i; j 1.2素数筛选（筛选出小于等于 MAXN的素数） /* *素数筛选，存在小于等于MAXN的素数 * prime[0]存的是素数的个数 */ constint MAXN=10000; int prime[MAXN+1]; void getPrime() { memset(prime,0,sizeof(prime)); for(int i=2; i<=MAXN; i++) { if(!prime[i])prime[++prime[0]]=i; for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) { prime[prime[j]*i]=1; if(i%prime[j]==0)break; } } } 1.3大区间素数筛选（POJ2689） /* * POJ 2689 Prime Distance *给出一个区间[L,U]，找出区间内容、相邻的距离最近的两个素数和 *距离最远的两个素数。 * 1<=L #include memset(prime,0,sizeof(prime)); for(int i=2; i<=MAXN; i++) { if(!prime[i])prime[++prime[0]]=i; for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) { prime[prime[j]*i]=1; if(i%prime[j]==0)break; } } } bool notprime[1000010]; int prime2[1000010]; void getPrime2(int L,int R) { memset(notprime,false,sizeof(notprime)); if(L<2)L=2; for(int i=1; i<=prime[0]&&(longlong)prime[i]*prime[i]<=R;i++) { int s=L/prime[i]+(L%prime[i]>0); if(prime2[0]<2)printf(\); else { int x1=0,x2=100000000,y1=0,y2=0; for(int i=1; i if(prime2[i+1]-prime2[i] x1=prime2[i]; x2=prime2[i+1]; } if(prime2[i+1]-prime2[i]>y2-y1) { y1=prime2[i]; y2=prime2[i+1]; } } printf(\distant.\\n\,x1,x2,y1,y2); } } } 2、素数筛选和合数分解 //****************************************** //素数筛选和合数分解 constint MAXN=10000; int prime[MAXN+1]; void getPrime() { memset(prime,0,sizeof(prime)); for(int i=2; i<=MAXN; i++) { if(!prime[i])prime[++prime[0]]=i; for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) { prime[prime[j]*i]=1; if(i%prime[j]==0)break; } } } longlong factor[100][2]; int fatCnt; int getFactors(longlong x) { fatCnt=0; longlong tmp=x; for(int i=1; prime[i]<=tmp/prime[i]; i++) { factor[fatCnt][1]=0; if(tmp%prime[i]==0) { factor[fatCnt][0]=prime[i]; while(tmp%prime[i]==0) { factor[fatCnt][1]++; tmp/=prime[i]; } fatCnt++; } } if(tmp!=1) { factor[fatCnt][0]=tmp; 8