《算法竞赛进阶指南》 0x14 ~ 0x16 代码 + 杂谈

哈希

雪花

1. hash表 做法

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 99991;
int snow[N][7], head[N], nxt[N];
int n, cnt;

int H(int *a){
    int sum = 0, mul = 1;
    for(int i = 0; i <= 6; i ++ ){
        sum = (sum + a[i]) % mod;
        mul = (ll)mul * a[i] % mod;
    }
    return (sum + mul) % mod;
} // hash 函数 他们的长度和 长度积 必然一样

bool chk(int *a, int *b){
    for(int i = 0; i < 6; i ++ ) {
        for(int j = 0; j < 6; j ++ ) {
            bool ok = 1;
            for(int k = 0; k < 6; k ++) 
                if(a[(i + k) % 6] != b[(j + k) % 6]) ok = 0;
            if(ok) return 1;
            ok = 1;
            for(int k = 0; k < 6; k ++ ) 
                if(a[(i + k) % 6] != b[(j - k + 6) % 6]) ok = 0;
            if(ok) return 1;
        }
    }
    return 0;
}

bool ins(int *a){
    int val = H(a);
    for(int i = head[val]; i; i = nxt[i]){
        if(chk(snow[i], a)) return 1;
    }
    ++ cnt;
    for(int i = 0; i < 6; i ++) snow[cnt][i] = a[i];
    nxt[cnt] = head[val];
    head[val] = cnt;
    return 0;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ) {
        int a[10];
        for(int j = 0; j < 6; j ++ ) cin >> a[j];
        if(ins(a)) {
            cout << "Twin snowflakes found." << endl;
            return 0;
        }
    }
    cout << "No two snowflakes are alike." << endl;
}

1. 最小表达法 做法
   写的好乱。。。。orz

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1e6 + 5 ;
const int mod = 991 ;
int s[300],ss[300];

int ge(int s[]) {
	int len = 6;
	for(int i=1; i<=len; i++) s[i+len]=s[i];
	int i=1,j=2,k;
	while(i<=len&&j<=len) {
		for(k=0; k<len&&s[i+k]==s[j+k]; k++);
		if(k==len) break;
		if(s[k+i]>s[j+k]) {
			i=i+1+k;
			if(i==j) i++;
		} else {
			j=j+1+k;
			if(j==i) j++;
		}
	}
	int pos=min(i,j);
	return pos;
}

set<int> mp;

signed main() {
	int n;
	cin>>n;
	while(n--) {
		for(int i=1; i<=6; i++) {
			cin>>s[i];
		}
		for(int i=1;i<=6;i++) ss[7-i]=s[i];
		int hash = 0;
		int k1=ge(s);
		for(int i=0;i<6;i++) {
			hash=hash*mod+s[k1+i];	
		}
		
		int k2=ge(ss);
		int hash2=0;
		for(int i=0;i<6;i++){
			hash2=hash2*mod+ss[k2+i];
		 }
		if(mp.find(min(hash,hash2))!=mp.end()) {
			cout<<"Twin snowflakes found."<<endl;
			return 0;
		}
		mp.insert(min(hash,hash2));
	}
	cout<<"No two snowflakes are alike."<<endl;
	return 0;
}

兔子兔子 进制hash
数学 可以直接减出来内部连续字串

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int unsigned long long

const int maxn = 1e6 + 5 ;
const double pi = acos(-1.0);
const int mod = 131;

char str[maxn];
int p[maxn],f[maxn];
int n;

signed main() {
	scanf("%s",str+1);
	int len = strlen(str+1);
	p[0]=1;
	for(int i=1; i<=len; i++) {
		f[i]=f[i-1]*131+(str[i]-'a'+1);
		p[i]=p[i-1]*mod;
	}
	cin>>n;
	while(n--) {
		int l,r,x,y;
		cin>>x>>y>>l>>r;
		if(f[y]-f[x-1]*p[y-x+1]==f[r]-f[l-1]*p[r-l+1]) {
			cout<<"Yes"<<endl;
		} else cout<<"No"<<endl;
	}
	return 0;
}

回文

1. 马拉车 （On）
2. 二分 + hash
   算出一个前缀和,再算出一个后缀和,然后就可以知道,正字符串和一个反字符串.字符串的哈希值就是这个区间的哈希值和.
   算完之后,我们当前就只需要枚举一个mid中间点,因为所有回文串都是有一个中间点(奇),或者中间区间(偶),然后二分分别寻找这个字符串长度即可。

const int maxn=1e6+5;
char s[maxn*2],str[maxn*2];
int Len[maxn*2],len;
void getstr() {
	int k=0;
	str[k++]='@';
	for(int i=0; i<len; i++)
		str[k++]='#',str[k++]=s[i];
	str[k++]='#';
	len=k;
	str[k]=0;
}
void manacher() {
	int mx=0,id;
	for(int i=1; i<len; i++) {
		if(mx>i) Len[i]=min(Len[2*id-i],mx-i);
		else Len[i]=1;
		while(str[i+Len[i]]==str[i-Len[i]])
			Len[i]++;
		if(Len[i]+i>mx)
			mx=Len[i]+i,id=i;
	}
}
int main() {
	scanf("%s",s);
	len=strlen(s);
	getstr();
	manacher();
	int ans=1;
	for(int i=1; i<len; i++) ans=max(ans,Len[i]);
	printf("%d\n",ans-1);
	return 0;
}

SA 待续

KMP

//得到字符串str的next数组
//最小循环节（len / (len-next[len])） 
// len % (len - nxt[len]) == 0 len 位置是个循环点位
void get_next(char str[]){
    memset(a,0,sizeof(a));
    int i = 0,j = -1;
    a[0] = -1;
    while(i < s){
        if(j == -1 || str[i] == str[j]){
            i++;
            j++;
            a[i] = j;
        }
        else
            j = a[j];
    }
}
// p 71 f数组 == 字串长度便是一次出现
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    	char str[maxn];
    	scanf("%s",str);
    	s = strlen(str);
    	get_next(str);
    	int k = s - a[s];
    	int ans = s / k;//ans是最小循环节
    	if(ans == 1) printf("%d\n",k*2-s);
    	else{
    		ans = (s%k?ans+1:ans);
    		printf("%d\n",k*ans-s);
		}
	}
	return 0;
} 

周期

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5 ;

int n, m;
char str[maxn];
int nxt[maxn];

void getnxt() {
	nxt[1]=0;
	for(int i=2,j=0; i<=n; i++) {
		while(j>0&&str[i]!=str[j+1]) j=nxt[j];
		if(str[i]==str[j+1]) j++;
		nxt[i]=j;
	}
}

signed main() {
	int id=0;
	while(cin>>n,n) {
		cin>>(str+1);
		getnxt();
		cout<<"Test case #"<<++id<<endl;
		for(int i=2;i<=n;i++){
			if(i%(i-nxt[i])==0&&(i/(i-nxt[i]))>1){
				cout<<i<<" "<<i/(i-nxt[i])<<endl;
			}
		}
		cout<<endl;	
	}
	return 0;
}

0x16

前缀统计 板子。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int trie[maxn][30],tot=1;
int ens[maxn];

void ins(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]; 
	}
	ens[p]++;
}

int serach(char str[]){
	int res=0;
	int len=strlen(str),p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		if(trie[p][ch]==0) break;
		p=trie[p][ch];
		if(ens[p]) res+=ens[p];
	}
	return res;
}

signed main() {
	int n,m;
	cin>>n>>m;
	char s[maxn];
	for(int i=1;i<=n;i++){
		cin>>s;
		ins(s);
	}
	while(m--){
		int ans=0;
		cin>>s;
		ans+=serach(s);
		cout<<ans<<endl;
	}
	return 0;
}

剩下2个 这里不再整理 拿之前写的 链接
https://blog.csdn.net/qq_40831340/article/details/90644908