声明

本人在理解kuangbin的模板之后写下注释，如有错请谅解，可留言告诉我错误谢谢；
附上kuangbin的一些网站：
kuangbin的ACM模板：https://kuangbin.github.io/2018/08/01/ACM-template/
kuangbin的博客：https://kuangbin.github.io
kuangbin的博客园：https://www.cnblogs.com/kuangbin/
kuangbin的GitHub：https://github.com/kuangbin

1、字符串处理

1.1、KMP

  1. #include<stdio.h>
  2. #include<string.h>
  4. /*
  5.  * man[]    主串
  6.  * pat[]    模式串
  7.  * next[i]  失配数组,数组值为模式串前 i 项构成的子串前缀后缀相同部分长度的最大值
  8.  * 
  9.  * kmpPre(pat[],patlen,next[])
  10.  *     以 i 和 j 为指针,模式串跟自己进行匹配,构建失配数组以方便模式串在主串中配对时进行跳转
  11.  * kmpCount(pat[],patlen,man[],manlen)
  12.  *     以 i 和 j 为指针,模式串在失配数组的辅助下在主串中进行匹配,输出模式串在主串中出现的次数 ans
  13.  */
  15. int next[10010];
  16. void kmpPre(char pat[], int patLen, int next[]){
  17.     int i,j;
  18.     i=0; j=next[0]=-1;
  19.     while(i<patLen){
  20.         while(j!=-1 && pat[i]!=pat[j]) j=next[j];
  21.         i++; j++;
  22.         next[i]=j;
  23.     }
  24. }
  25. int kmpCount(char pat[], int patLen, char man[], int manLen){
  26.     int i,j;
  27.     int ans=0;
  28.     kmpPre(pat,patLen,next);
  29.     i=j=0;
  30.     while(i<manLen){
  31.         while(j!=-1 && man[i]!=pat[j]) j=next[j];
  32.         i++; j++;
  33.         if(j>=patLen){
  34.             ans++;
  35.             j=next[j];
  36.         }
  37.     }
  38.     return ans;
  39. }
  41. int main(){
  42.     char man[]={"ababababca"};
  43.     char pat[]=   {"abababca"};
  44.     int ans=kmpCount(pat,strlen(pat),man,strlen(man));
  45.     printf("%d\n", ans);
  46.     return 0;
  47. }

1.3、manacher

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  6. /*
  7.  * MAXN  原字符串长度
  8.  * str[]  原字符串
  9.  * ma[]  加工串,填充处理后的字符串
  10.  * mp[i]  以 ma[] 为模板,当前位置 i 为子回文串中心,值为该回文串半径长度
  11.  * '$'  开头占位符
  12.  * '#'  字符间占位符
  13.  * mx 代表当前<已经匹配完毕的结尾最远的回文串>到达了ma[]数组的第mx位
  14.  * id 代表当前<已经匹配完毕的结尾最远的回文串>中心为ma[]数组的第id位
  15.  * 
  16.  * Mp[i]=1，说明Mx没有覆盖超过i，那么Mx的値在这一步执行后一定会增加
  17.  * Mp[i]=Mx-i,说明以Ma[i]为中心的回文串至少到达了Mx，那么Mx的値在这之后不会减少
  18.  * Mp[i]=Mp[ID*2-i],说明Ma[i]已经匹配不下去了
  19.  * 
  20.  * str[i]:     a   b   a   a    b     a
  21.  * i:      0 1 2 3 4 5 6 7 8 9 10 11 12 13  14
  22.  * ma[i]:  $ # a # b # a # a #  b  #  a  #  /0
  23.  * mp[i]:  1 1 2 1 4 1 2 7 2 1  4  1  2  1
  24.  */
  26. const int MAXN=100;
  27. char str[MAXN], ma[MAXN*2];
  28. int mp[MAXN*2];
  29. void manacher(int sLen){
  30.     int maCount=0;
  31.     ma[maCount++]='$';
  32.     ma[maCount++]='#';
  33.     for(int i=0; i<sLen; i++){
  34.         ma[maCount++]=str[i];
  35.         ma[maCount++]='#';
  36.     }
  37.     ma[maCount]=0;
  38.     int mx=0;
  39.     int id=0;
  40.     for(int i=0; i<maCount; i++){
  41.         mp[i]=mx>i?min(mp[2*id-i],mx-i):1;
  42.         while(ma[i+mp[i]]==ma[i-mp[i]])
  43.             mp[i]++;
  44.         if(i+mp[i]>mx){
  45.             mx=i+mp[i];
  46.             id=i;
  47.         }
  48.     }
  49. }
  51. int main(){
  52.     while (scanf("%s", str) == 1){
  53.         int sLen=strlen(str);
  54.         manacher(sLen);
  55.         int ans=0;
  56.         for (int i=0; i<2*sLen+2; i++)
  57.             ans=max(ans,mp[i]-1);
  58.         printf("%d\n", ans);
  59.     }
  60.     return 0;
  61. }

1.4、AC自动机

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <string.h>
  5. #include <queue>
  6. using namespace std;
  8. /*
  9.  * MAXN   字典树节点序号总数
  10.  * root   根节点序号,一直为0
  11.  * L      为当前节点序号
  12.  * buf[]  临时存储字符串(模式串和文章)
  13.  * next[i][j]
  14.  *     节点连接数组，i 为字典树当前节点序号,j 为该节点字母序号,数组值为相对应下一个字典树节点的序号(靠左节点优先赋值)
  15.  * fail[i]
  16.  *     失配数组，i 为字典树当前节点序号,数组值为当前节点相对应下一个字典树节点失配后跳转到的字典树节点序号{a->a)
  17.  * end[i]
  18.  *     单词尾部加数，字典树当前节点序号为 i,数组值为以当前节点为结尾的单词数(大多数时候为1)
  19.  * 
  20.  * init()        初始化字典树建立根
  21.  * newnode()     建立新节点
  22.  * insert(buf[]) now 为当前节点序号,向字典树中装入模式串
  23.  * build()       用队列 Q 依次存节点序号，构建失配数组方便查询
  24.  * query(buf[])  输入文章，输出 n 个模式串在文章中出现的个数(?/n个)
  25.  */
  27. const int MAXN=500010;
  28. struct Trie{
  29.     int next[MAXN][26], fail[MAXN], end[MAXN];
  30.     int root, L;
  31.     void init(){
  32.         L = 0;
  33.         root = newnode();
  34.     }
  35.     int newnode(){
  36.         for (int i = 0; i < 26; i++)
  37.             next[L][i] = -1;
  38.         end[L++] = 0;
  39.         return L - 1;
  40.     }
  41.     void insert(char buf[]){
  42.         int len = strlen(buf);
  43.         int now = root;
  44.         for (int i = 0; i < len; i++){
  45.             if (next[now][buf[i] - 'a'] == -1)
  46.                 next[now][buf[i] - 'a'] = newnode();
  47.             now = next[now][buf[i] - 'a'];
  48.         }
  49.         end[now]++;
  50.     }
  51.     void build(){
  52.         queue<int> Q;
  53.         fail[root] = root;
  54.         for (int i = 0; i < 26; i++)
  55.             if (next[root][i] == -1)
  56.                 next[root][i] = root;
  57.             else{
  58.                 fail[next[root][i]] = root;
  59.                 Q.push(next[root][i]);
  60.             }
  61.         while (!Q.empty()){
  62.             int now = Q.front();
  63.             Q.pop();
  64.             for (int i = 0; i < 26; i++)
  65.                 if (next[now][i] == -1)
  66.                     next[now][i] = next[fail[now]][i];
  67.                 else{
  68.                     fail[next[now][i]] = next[fail[now]][i];
  69.                     Q.push(next[now][i]);
  70.                 }
  71.         }
  72.     }
  73.     int query(char buf[]){
  74.         int len = strlen(buf);
  75.         int now = root;
  76.         int res = 0;
  77.         for (int i = 0; i < len; i++){
  78.             now = next[now][buf[i] - 'a'];
  79.             int temp = now;
  80.             while (temp != root){
  81.                 res += end[temp];
  82.                 end[temp] = 0;
  83.                 temp = fail[temp];
  84.             }
  85.         }
  86.         return res;
  87.     }
  88.     void debug(){
  89.         for (int i = 0; i < L; i++){
  90.             printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], end[i]);
  91.             for (int j = 0; j < 26; j++)
  92.                 printf("%2d", next[i][j]);
  93.             printf("]\n");
  94.         }
  95.     }
  96. };
  98. char buf[1000010];
  99. Trie ac;
  101. int main(){
  102.     int T;
  103.     int n;
  104.     scanf("%d", &T);
  105.     while (T--){
  106.         scanf("%d", &n);
  107.         ac.init();
  108.         for (int i = 0; i < n; i++){
  109.             scanf("%s", buf);
  110.             ac.insert(buf);
  111.         }
  112.         ac.build();
  113.         scanf("%s", buf);
  114.         printf("%d\n", ac.query(buf));
  115.     }
  116.     return 0;
  117. }

2、数学

2.1、素数

2.1.1 素数筛选（判断 <MAXN 的数是否素数）

  1. /* 
  2.  * MAXN 判断是否为素数的最大值
  3.  * notprime[i] i 为所指数字，其值为 false 表示为素数，true 表示不为素数
  4.  * 
  5.  * 素数：指在大于1的自然数中，只有1和它本身能整除的数
  6.  * 存储小于 MAXN 的数是不是素数这一状态
  7.  */
  8. #include<cstring>
  9. const int MAXN = 1000010;
  10. bool notprime[MAXN];
  11. void init(){
  12.     memset(notprime, false, sizeof(notprime));
  13.     notprime[0] = notprime[1] = true;
  14.     for (int i = 2; i < MAXN; i++)
  15.         if (!notprime[i]){
  16.             //防止后面 i*i 溢出 (或者 i,j 用 long long)
  17.             if (i > MAXN / i)
  18.                 continue;
  19.             //直接从 i*i 开始就可以，小于 i 倍的已经筛选过了, 注意是 j+=i
  20.             for (int j = i * i; j < MAXN; j += i)
  21.                 notprime[j] = true;
  22.         }
  23. }