哈希
雪花
- 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;
}
- 最小表达法 做法
写的好乱。。。。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;
}
回文
- 马拉车 （On）
- 二分 + 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
京公网安备 11010502036488号