文章目录

• • 前言
• 其他
• • 快读快输
  • 卡常
  • $DataMaker$
• 字符串模板
• • KMP
  • 字符串hash
  • Trie
  • 最小表示法
  • Manacher
  • AC自动机
  • SA
  • SAM
  • 广义SAM
  • PAM
• 其他模板
• • 凸包
  • 模拟退火

前言

因为老是懒得打模板的时候老是扣不到自己的标(因为之前的都打得太丑了)，所以导致我十分的不爽。便打算开一个模板库。会不断更新的

---

其他

快读快输

int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; } void print(int x){if (x>9) print(x/10); putchar(x%10+48); return; }

卡常

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") %:pragma GCC optimize("-fgcse") %:pragma GCC optimize("-fgcse-lm") %:pragma GCC optimize("-fipa-sra") %:pragma GCC optimize("-ftree-pre") %:pragma GCC optimize("-ftree-vrp") %:pragma GCC optimize("-fpeephole2") %:pragma GCC optimize("-ffast-math") %:pragma GCC optimize("-fsched-spec") %:pragma GCC optimize("unroll-loops") %:pragma GCC optimize("-falign-jumps") %:pragma GCC optimize("-falign-loops") %:pragma GCC optimize("-falign-labels") %:pragma GCC optimize("-fdevirtualize") %:pragma GCC optimize("-fcaller-saves") %:pragma GCC optimize("-fcrossjumping") %:pragma GCC optimize("-fthread-jumps") %:pragma GCC optimize("-funroll-loops") %:pragma GCC optimize("-fwhole-program") %:pragma GCC optimize("-freorder-blocks") %:pragma GCC optimize("-fschedule-insns") %:pragma GCC optimize("inline-functions") %:pragma GCC optimize("-ftree-tail-merge") %:pragma GCC optimize("-fschedule-insns2") %:pragma GCC optimize("-fstrict-aliasing") %:pragma GCC optimize("-fstrict-overflow") %:pragma GCC optimize("-falign-functions") %:pragma GCC optimize("-fcse-skip-blocks") %:pragma GCC optimize("-fcse-follow-jumps") %:pragma GCC optimize("-fsched-interblock") %:pragma GCC optimize("-fpartial-inlining") %:pragma GCC optimize("no-stack-protector") %:pragma GCC optimize("-freorder-functions") %:pragma GCC optimize("-findirect-inlining") %:pragma GCC optimize("-fhoist-adjacent-loads") %:pragma GCC optimize("-frerun-cse-after-loop") %:pragma GCC optimize("inline-small-functions") %:pragma GCC optimize("-finline-small-functions") %:pragma GCC optimize("-ftree-switch-conversion") %:pragma GCC optimize("-foptimize-sibling-calls") %:pragma GCC optimize("-fexpensive-optimizations") %:pragma GCC optimize("-funsafe-loop-optimizations") %:pragma GCC optimize("inline-functions-called-once") %:pragma GCC optimize("-fdelete-null-pointer-checks")

$DataMaker$

#include<cstdlib> #include<string> #include<ctime> #include<iostream> using namespace std; int t; string s; int random(int x) {return 1+(long long)rand()*rand()*rand()*rand()%x;} int main() {srand((unsigned long long)time(0));scanf("%d",&t);for(int ti=1;ti<=t;ti++){s="data";if (ti>=10) s+=ti/10+48;s+=ti%10+48;s+=".in";freopen(s.c_str(),"w",stdout);fclose(stdout);} }

---

字符串模板

KMP

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1e6+7; int next[maxn]; char s2[maxn],s1[maxn]; void spawn_next(char* st) {int l=strlen(st),k=0;next[0]=-1;for(int i=0; i<l; i++){k=next[i];while(k!=-1&&st[i]!=st[k]) k=next[k];next[i+1]=++k;} } int match(char* st,char* s) {int l1=strlen(st),l2=strlen(s);int k=0;for(int i=0; i<l1; i++){while(k!=-1&&st[i]!=s[k]) k=next[k];if(st[i]==s[k]) k++;if(k==l2) return i-l2+1;} } int kmp(char* st,char* s) {spawn_next(st); return match(st,s); } int main() {scanf("%s%s",s1,s2);int ass=kmp(s1,s2)+1;printf("%d",ass); }

字符串hash

#include<cstdio> #include<iostream> #include<string> #define p 30001 using namespace std; int n,ans; string s,hash[p]; int hashmath(string x) {int ans=0;for (int i=0;i<x.size();i++){ans=(ans+x[i])%p;}return ans%p; } int locate(string x) {int wz=hashmath(x);int i=0;while (i<p && hash[(wz+i)%p]!=x && hash[(wz+i)%p]!="")i++;return (wz+i)%p; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){cin>>s;int wz=locate(s);if(hash[wz]!=s){hash[wz]=s;ans++;}}printf("%d",ans); }

Trie

#include<cstdio> #include<cstring> using namespace std; int n,tot,m,l[800000][26];; char s[101]; bool pre[800000],ok[800000]; void insert(char *s)//插入 {int len=strlen(s),now=0;for(int i=0;i<len;i++){int ch=s[i]-'a';if(!l[now][ch]) l[now][ch]=++tot;//新建节点now=l[now][ch];//下一个点}pre[now]=true;return; } void find(char *s) {int len=strlen(s),now=0;for(int i=0;i<len;i++){int ch=s[i]-'a';if(!l[now][ch])//错误匹配{printf("WRONG\n");return;}now=l[now][ch];}if(!pre[now]) printf("WRONG\n");//错误匹配else if(ok[now]) printf("REPEAT\n");//重复匹配else {printf("OK\n");ok[now]=true;}//正确匹配和标记return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s);insert(s);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s",s);find(s);}return 0; }

最小表示法

#include<cstdio> #include<algorithm> using namespace std; int n,a[600010],ans; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];int i=1,j=2,k;while(i<=n&&j<=n){for(k=0;k<=n&&a[i+k]==a[j+k];k++);//找不同if(k==n) break;//全一个if(a[i+k]>a[j+k]){i=i+k+1;if(i==j) i++;}else{j=j+k+1;if(i==j) j++;}}ans=min(i,j);//取最小for(i=ans;i<ans+n;i++)printf("%d ",a[i]);//输个出 }

Manacher

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=11100000; int n,ans,hw[2*N]; char re[N],s[2*N]; void Manacher() {int mid=0,maxright=0;for(int i=1;i<=n;i++){if(i<=maxright)hw[i]=min(hw[2*mid-i],hw[mid]+mid-i);else hw[i]=1;while(s[i-hw[i]]==s[i+hw[i]]) hw[i]++;if(i+hw[i]>maxright){maxright=i+hw[i];mid=i;}ans=max(ans,hw[i]);} } int main() {scanf("%s",re+1);n=strlen(re+1);s[0]=s[1]='#';for(int i=1;i<=n;i++){s[i*2]=re[i];s[i*2+1]='#';}n=n*2+2;s[n]=0;Manacher();printf("%d",ans-1); }

AC自动机

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e6+100; int n,ans; char s[N]; struct ACmac{int fail[N],son[N][30],siz[N],cnt;queue<int> q;void Make(char *s){int x=1,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'a';if(!son[x][c]){son[x][c]=++cnt;memset(son[cnt],0,sizeof(son[cnt]));}x=son[x][c];}siz[x]++;return;}void Bfs(){for(int i=0;i<26;i++)son[0][i]=1;q.push(1);fail[1]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<26;i++){if(!son[x][i]) son[x][i]=son[fail[x]][i];else{q.push(son[x][i]);int y=fail[x];fail[son[x][i]]=son[y][i];}}}}void Find(char *s){int x=1,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'a',k=son[x][c];while(k>1&&siz[k]){ans+=siz[k];siz[k]=0;k=fail[k];}x=son[x][c];}return;} }Ac; int main() {scanf("%d",&n);Ac.cnt=1;for(int i=0;i<26;i++)Ac.son[0][i]=1,Ac.son[1][i]=0;for(int i=1;i<=n;i++){scanf("%s",s);Ac.Make(s);}Ac.Bfs();scanf("%s",s);Ac.Find(s);printf("%d\n",ans); }

SA

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+10; int n,m,sa[N],x[N],y[N],c[N]; char s[N]; void Qsort(){//基数排序for(int i=1;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0; } void Get_SA(char *s) {for(int i=1;i<=n;i++)//将第一位获取位第一关键字x[i]=s[i]-'0'+1,y[i]=i;Qsort();for(int w=1;w<=n;w<<=1){int p=0;for(int i=n-w+1;i<=n;i++)y[++p]=i;//将2*w位后已经没有的先丢到前面for(int i=1;i<=n;i++)//每个对应到其i-w的第二关键字if(sa[i]>w) y[++p]=sa[i]-w;Qsort();swap(x,y);//排序x[sa[1]]=p=1;for(int i=2;i<=n;i++)//确定新的排名并判断排序是否结束x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;if(p==n) break;m=p;}return; } int main() {scanf("%s",s+1);n=strlen(s+1);m=100;Get_SA(s);for(int i=1;i<=n;i++)printf("%d ",sa[i]);return 0; }

SAM

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e6+10; int n,cnt,num[N],len[N],fail[N],next[N][26],ans; char s[N]; void New_Point(int x,int y){next[x][y]=++cnt;len[cnt]=len[x]+1; } void Make_SAM(char *s){int last;cnt=last=num[1]=1;for(int i=1;i<=n;i++){int val=s[i]-'a';New_Point(last,val);int x=last,y;last=next[x][val];for(y=fail[x];y;y=fail[y])if(!next[y][val]) next[y][val]=last;else{if(len[y]+1==len[next[y][val]])fail[last]=next[y][val];else{int z=next[y][val];New_Point(y,val);fail[cnt]=fail[z];num[cnt]=num[z];fail[last]=fail[z]=cnt;for(int i=0;i<26;i++)next[cnt][i]=next[z][i];for(int w=y;w;w=fail[w])if(next[w][val]==z)next[w][val]=cnt;}break;}if(!y)fail[last]=1;for(y=last;y;y=fail[y])num[y]++;}return; } int main() {scanf("%s",s+1);n=strlen(s+1);Make_SAM(s);for(int i=1;i<=cnt;i++)if(num[i]>1)ans=max(ans,num[i]*len[i]);printf("%d",ans); }

广义SAM

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e6+10; ll n,m,cnt,last,len[N],fa[N],ch[N][26],ans; char s[N]; ll Ins(ll c,ll last){ll p=last;if(ch[p][c]){ll q=ch[p][c];if(len[p]+1==len[q])return q;else{ll nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;return nq;}}ll np=++cnt;len[np]=len[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{ll q=ch[p][c];if(len[p]+1==len[q])fa[np]=q;else{ll nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}return np; } int main() {scanf("%lld",&m);cnt=1;for(ll i=1;i<=m;i++){last=1;scanf("%s",s);n=strlen(s);for(ll j=0;j<n;j++)last=Ins(s[j]-'a',last);}for(ll i=1;i<=cnt;i++)ans+=len[i]-len[fa[i]];printf("%lld",ans); }

PAM

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e6+10; int n,len[N],fail[N],num[N],next[N][26],cnt,m,last; char s[N]; int get_fail(int x){for(;s[n-len[x]-1]!=s[n];)x=fail[x];return x; } int Insert(){int x=get_fail(last);if(!next[x][s[n]]){len[++cnt]=len[x]+2;int y=get_fail(fail[x]);fail[cnt]=next[y][s[n]];num[cnt]=num[fail[cnt]]+1;next[x][s[n]]=cnt;}return (last=next[x][s[n]]); } int main() {scanf("%s",s+1);m=strlen(s+1);s[0]=26;len[1]=-1;fail[0]=cnt=1;int k=0;for(n=1;n<=m;n++){s[n]=(s[n]-'a'+k)%26;printf("%d ",k=num[Insert()]);} }

---

其他模板

凸包

#include<cstdio> #include<algorithm> #include<cmath> #define N 10010 using namespace std; struct point{double x,y; }a[N]; int n,s[N]; double ans; double m(point x,point y,point z) {return (x.x-z.x)*(y.y-z.y)-(y.x-z.x)*(x.y-z.y);} double dis(point x,point y) {return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));} bool cmp(point x,point y) {double t=m(x,y,a[1]);if(t>0||t==0&&dis(x,a[1])<dis(y,a[1]))return true;else return false; } void init() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf",&a[i].x,&a[i].y);if(a[i].y<a[1].y||a[i].y==a[1].y&&a[i].x<a[1].x)swap(a[i],a[1]);}sort(a+2,a+1+n,cmp); } void praham() {s[1]=1;s[2]=2;s[3]=3;int top=3;for(int i=4;i<=n;i++){while(m(a[i],a[s[top]],a[s[top-1]])>=0)top--;s[++top]=i;}for(int i=1;i<top;i++)ans+=dis(a[s[i]],a[s[i+1]]);printf("%.2lf",ans+dis(a[s[1]],a[s[top]])); } int main() {init();praham(); }

模拟退火

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; const int N=1100; const double Delit=0.993; int n;double x[N],y[N],v[N],ansx,ansy,ans; double calc(double nx,double ny){double ans=0;for(int i=1;i<=n;i++){double zx=x[i]-nx,zy=y[i]-ny;ans+=sqrt(zx*zx+zy*zy)*v[i];}return ans; } void S_A(){double x=ansx,y=ansy;double t=2000;while(t>1e-14){double nx=x+((rand()<<1)-RAND_MAX)*t;double ny=y+((rand()<<1)-RAND_MAX)*t;double now=calc(nx,ny),k=now-ans; double now=calc(nx,ny),k=now-ans;printf("%d %lf %lf %lf\n",rand(),nx,ny,now);break;if(k<0){ans=now;x=nx;y=ny;ansx=nx;ansy=ny;}else if(exp(-k/t)*RAND_MAX>rand())x=nx,y=ny;t=t*Delit;}return; } void Solve(){ansx/=n;ansy/=n;ans=calc(ansx,ansy);S_A();S_A();S_A();return; } int main() {srand(19260817);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf%lf%lf",&x[i],&y[i],&v[i]);ansx+=x[i];ansy+=y[i];}Solve();printf("%.3lf %.3lf",ansx,ansy); }

总结

以上是生活随笔为你收集整理的亿些模板【字符串+其他】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。