JZTXT

算法模板

发布时间 2023-08-25 16:25:54作者: Alric

快速幂

int power(int a,int b,int p){
	int ans=1%p;
	for(;b;b>>=1){
		if(b&1)ans=(long long)ans*a%p;
		a=(long long)a*a%p;
	}
	return ans;
}

快速乘

long long mul(long long a,long long b,long long p){
    long long ans=0;
    for(;b;b>>=1){
        if(b&1)ans=(ans+a)%p;
        a=a*2%p;
    }
    return ans;
}

ST表

void ST_prework(){
	for(int i=1;i<=n;i++)f[i][0]=a[i];
	int t=log(n)/log(2)+1;
	for(int j=1;j<t;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int ST_query(int l,int r){
	int k=log(r-l+1)/log(2);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}

KMP

nxt[1]=0;
for(int i=2,j=0;i<=n;i++){
	while(j>0&&a[i]!=a[j+1])j=nxt[j];
	if(a[i]==a[j+1])j++;
	nxt[i]=j;
}
for(int i=1,j=0;i<=m;i++){
	while(j>0&&(j==n||b[i]!=a[i+1]))j=nxt[j];
	if(b[i]==a[j+1])j++;
	f[i]=j;
}

最小表示法

int n=strlen(s+1);
for(int i=1;i<=n;i++)s[n+i]=s[i];
int i=1,j=2,k;
while(i<=n&&j<=n){
	for(k=0;k<n&&s[i+k]==s[j+k];k++);
	if(k==n)break;
	if(s[i+k]>s[j+k]){
		i=i+k+1;
		if(i==j)i++;
	}else{
		j=j+k+1;
		if(i==j)j++;
	}
}
ans=min(i,j);

Trie

int trie[SIZE][26],tot=1;
void insert(char *str){
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		if(trie[p][ch]==0)trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	end[p]=true;
}
bool search(char* str){
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		p=trie[p][str[k]-'a'];
		if(p==0)return false;
	}
	return end[p];
}