主页
Featured image of post ACM学习笔记 - 总模板……

ACM学习笔记 - 总模板……

总结出来的个人向的一些模板……

文章字数:5816
预计阅读时长: 分钟

该笔记目前直接复制的之前的笔记,还未调整格式。页面格式、内容、链接等可能存在混乱错误……

线性筛素数

  • 用途:对一定范围\(n\)内的数,构造素数表。

  • 注意点:ifNot_Prime数组范围为数据大小的范围,并不是个数。

#define MAX_N 100000000 + 5
bool IfNot_Prime[MAX_N]; //0---素数 1---不是素数
int Prime[MAX_N], PNum;	//PNum:记录范围内有多少个素数

void Init(int N)
{
    for (register int Top=2; Top<=N/2+1; Top++)
    {
        if (!IfNot_Prime[Top]) Prime[++PNum]=Top;
        for (register int C=1; C<=PNum && Top*Prime[C] <= MAX; C++)
        {
            IfNot_Prime[Top*Prime[C]]=1;
            if (Top % Prime[C] == 0) break;
        }
    }
} 
  • 解释:

    Prime内存放\(1\sim n\)内的所有素数。
    ifNot_Prime内存放否以具体的数是否为素数。

快速幂

long long q_pow(long long base, long long idx)	//base 底数、index 指数
{
	long long answer = 1;
	while (idx)
	{
		if (idx & 1)
			answer = answer * base % MOD; //带模的运算
		base = base * base % MOD;
		idx >>= 1;
	}
	return answer;
}
//使用例:
{
	q_pow(3,12);	//3^12
}

拓展——矩阵快速幂

  • 用途:矩阵DP
//long long注意!……
#include <bits/stdc++.h>
#define matrix_MAX 100
#define MOD 1000000007
using namespace std;
struct typeMatrix
{
	long long mat[matrix_MAX + 1][matrix_MAX + 1] = {};
	int x, y;	//x——行,y——列

	typeMatrix(int x, int y) : x(x), y(y) {}

	inline typeMatrix operator*(const typeMatrix &a) const //矩阵乘法实现
	{
		typeMatrix res(x, a.y);
		for (int i = 1; i <= x; i++) //矩阵a(x1,y1);b(x2,y2),
		//新矩阵为res(x1,y2),做y1(或x2)次乘法累加
		for (int j = 1; j <= a.y; j++)
		for (int k = 1; k <= y; k++)
			res.mat[i][j] = (res.mat[i][j] + mat[i][k] * a.mat[k][j]) % MOD; //就矩阵乘法
		return res;
	}

	void initPowAns(int size)
	{
		for (int i = 1; i <= size; i++)
			mat[i][i] = 1;
			//注意标准快速幂中初始化为令ans=1,换成矩阵后初始化为令主对角线为1……
	}

	inline typeMatrix operator^(long long power) const //快速幂实现
	{
		typeMatrix ans(y, y), base = *this;
		ans.initPowAns(y);
		while (power)
		{
			if (power & 1)
				ans = ans * base;
			base = base * base;
			power >>= 1;
		}
		return ans;
	}
};
int main()
{
	long long n,k;

	scanf("%lld%lld", &n, &k);
	typeMatrix Matrix(n,n);	//定义矩阵
	/*读入矩阵*/
	typeMatrix ans = Matrix ^ k;
	/*输出结果矩阵*/
}

GCD&EXGCD

LL gcd(LL a, LL b)	//递归式gcd
{
    return b ? gcd(b, b % a) : a;
}
LL gcd_iteration(LL a, LL b)	//迭代式GCD
{
    while (b ^= a ^= b ^= a %= b);
    return a;
}
LL Exgcd_iteration(LL a, LL b, LL &x, LL &y)	//迭代式EXGCD
{
    x = 1, y = 0;       //初矩阵:1 0
    int x1 = 0, y1 = 1; //       0 1
    while (b)
    {
        int d = a / b;
        tie(x, x1) = make_tuple(x1, x - d * x1); //矩阵乘法
        tie(y, y1) = make_tuple(y1, y - d * y1);
        tie(a, b) = make_tuple(b, a - d * b); //迭代gcd()
    }
    return a;
}

并查集

并查集是一种树形的数据结构,顾名思义,它用于处理一些不交集的合并查询问题。

  • 用途:
    • 查找(Find):确定某个元素处于哪个子集。
    • 合并(Union):将两个子集合并成一个集合。
struct typeUnionFind
{
    int num, father[N], rank[N]; //这里rank作用是记录节点深度(真实为深度-1),采用了按秩合并的优化
    void init(int n)
    {
		num=n;
        for (int i = 1; i <= num; i++)
            father[i] = i;
    }

    inline int find(int node)	//查询操作
    {
        return father[node] == node ? node : (father[node] = find(father[node]));
		//这里使用了路径压缩优化
    }
    inline void merge(int node1, int node2)		//合并操作
    {
        int father1 = find(node1), father2 = find(node2);
        if (rank[father1] < rank[father2])
            father[father1] = father2;
        else if (rank[father1] > rank[father2])
            father[father2] = father1;
        else if (father1 != father2)
            father[father1] = father2, rank[father2]++;
			//如果深度一样且父节点不一样(不为一棵树),合并后新树深度会加一
    }
} UnionFind;
//使用例:
{
	//初始化
	UnionFind.init(n);

	UnionFind.merge(1,2);	//合并1,2这两个子集。
	UnionFind.find(3);		//查询3这个元素处于哪个子集。
}

ST表

用于处理区间最值询问问题。

#define MAX_N 100005
#define Work max //根据题目要求选择Work方式(最大还是最小)

int Log[MAX_N],	  //Log表
	Num[MAX_N],	  //存放原本数据的数组
	F[MAX_N][30], //ST表
	n;

void InitLog() //初始化Log数组
{
	Log[1] = 0, Log[2] = 1;
	for (int i = 3; i <= n; i++)
		Log[i] = Log[i / 2] + 1;
}
void Init()
{
	InitLog();
	for (int i = 1; i <= n; i++)
		F[i][0] = Num[i]; //刚开始f[n][0],即长度为1的序列中最小的就是它本身。
	//2开始,log2=1;log3=1;log4=2;log5=2;log6=2;log7=2;log8=3;
	for (int i = 2; i <= n; i++)
	{
		F[i][1] = Work(F[i][0], F[i - 1][0]);//这里特殊处理1,因为2^(1-1)=1,而2<<(1-1)=2
		for (int j = 2; j <= Log[i]; j++)
			F[i][j] = Work(F[i][j - 1], F[i - (1 << (j - 1))][j - 1]);
	}
}
int Find(int l, int r)
{
	int k = Log[r - l + 1];
	return Work(F[l + (1 << k) - 1][k], F[r][k]);
}
//使用例
{
	//初始化:先读入数据个数n,数组。
	Init();

	cout << Find(l, r); //输出[l,r]间的最值
}

线段树

直接放模板。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int L = 0, R = 1;

struct Message
{								  //节点维护的信息
	long long sum, len, add, mul; //区间和 区间长度 区间lazy的加法  区间lazy的乘法
	/*
	ans = ans*mul + add
	*/
	Message()
	{ //初始化函数
		sum = 0;
		add = 0;
		len = 0;
		mul = 1;
	}
	Message(long long xsum, long long xlen, long long xadd, long long xmul)
	{ //初始化函数
		sum = xsum;
		len = xlen;
		add = xadd;
		mul = xmul;
	}
	Message operator+(const Message &b)
	{ //定义 a+b
		Message p(sum + b.sum, len + b.len, 0, 1);
		return p;
	}
	/*
	(ans * mul + add) * famul + faadd 
	*/
	void modify(Message fa)
	{ //父亲的信息为fa , 父亲pushdown下传
		mul = mul * fa.mul;
		add = add * fa.mul + fa.add;
		sum = sum * fa.mul + fa.add;
	}
};

struct SegmentTree
{
	int l, r;	//当前管理区间 [l,r]
	int son[2]; //左儿子为 son[0] 右儿子为 son[1]
	Message x;
} node[N * 2];

void pushdown(int k)
{ //下传标记
	if (node[k].x.add != 0)
	{
		node[node[k].son[L]].x.modify(node[k].x);
		node[node[k].son[R]].x.modify(node[k].x);
		node[k].x.add = 0;
	}
}

void update(int k)
{ //更新节点k
	node[k].x = node[node[k].son[L]].x + node[node[k].son[R]].x;
}

int root, ini[N], cnt; //cnt 当前已经有了多少个节点
//假设数组初始时为ini

void buildTree(int &k, int l, int r)
{ //初始化一个管理[l,r]的节点 , 下标为k
	k = ++cnt;
	node[k].l = l;
	node[k].r = r;
	node[k].x.len = (r - l + 1); //初始化[l,r] //k = cnt+1; cnt++;
	if (l == r)//没有儿子了
	{
		node[k].x.sum = ini[l];
	}
	else //我是爸爸
	{
		int mid = (node[k].l + node[k].r) / 2; //儿子的左右分界
		buildTree(node[k].son[L], l, mid);	   //调用完后 左右儿子下表就可以被储存
		buildTree(node[k].son[R], mid + 1, r);
		update(k);
	}
}

Message work(int k, int ql, int qr, Message y)
{ //修改 [ql,qr] 顺带查询[ql,qr]
	if (ql <= node[k].l && node[k].r <= qr)
	{
		node[k].x.modify(y);
		return node[k].x;
	}
	else if (ql > node[k].r || qr < node[k].l)
		return ;
	else
	{
		Message p;
		pushdown(k);
		p = work(node[k].son[L], ql, mid, y) + work(node[k].son[R], mid + 1, qr, y);
		update(k);
		return p;
	}
}

int n, m;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &ini[i]);

	buildTree(root, 1, n);

	Message ans;

	//区间[l,r] += val
	int l, r, val;
	Message y;
	y.add = val;
	work(root, l, r, y);

	//区间[l,r] *= val
	Message y;
	y.mul = val;
	work(root, l, r, y);

	//查询区间[l,r]
	y.add = y.len = y.sum = 0;
	ans = work(root, l, r, y);
	cout << ans.sum << endl;
}

逆序对

用归并排序。
其中包含了对全排列的hash。

#define MAX_LENGTH 5000000

long long inver[MAX_LENGTH];	//记录每位的逆序对
template <typename T>
long long sortMerge_inv(T *rawArray, int indexLeft, int indexRight) //求逆序对版
{
    vector<T> tmpArray;
    long long sum = 0;
    if (indexLeft == indexRight)
        return 0;
    int mid = (indexLeft + indexRight) >> 1, 
		indexTmpArray = 0, 
		indexLeftMerge = indexLeft, 
		indexRightMerge = mid + 1;
    sum += sortMerge_inv(rawArray, indexLeft, mid);
    sum += sortMerge_inv(rawArray, mid + 1, indexRight);
    while (indexLeftMerge <= mid || indexRightMerge <= indexRight)
    {
        if (indexLeftMerge <= mid && (rawArray[indexLeftMerge] <= rawArray[indexRightMerge] 
			|| indexRightMerge > indexRight))
            tmpArray.push_back(rawArray[indexLeftMerge++]);
        else
        {
            tmpArray.push_back(rawArray[indexRightMerge++]), sum += mid - indexLeftMerge + 1;
            for (ALL(i, indexLeftMerge, mid)) //这里为注意点:为左部分的剩余所有数的逆序对个数++
                inver[i]++;
        }
    }
    for (ALL(i, indexLeft, indexRight))
        rawArray[i] = tmpArray[indexTmpArray++];
    return sum;
}

int hash_index[10];
long long fact(int num)
{
    long long ans = 1;
    for (ALL(i, 1, num))
        ans *= i;
    return ans;
}
void hash_init(int len)
{
    for (ALL(i, 1, len))
        hash_index[i] = len - i;
}
template <typename T>
//求全排列的Hash
long long sortMerge_hash(T *rawArray, int indexLeft, int indexRight, const int &length)
{
    if (indexLeft == indexRight)
        return 0;
    vector<T> tmpArray;
    vector<T> tmpFact; //用来swap后对位权的swap
    long long hashArr = 0;
    int mid = (indexLeft + indexRight) >> 1,
		indexTmpArray = 0,
		indexLeftMerge = indexLeft,
		indexRightMerge = mid + 1;
    hashArr += sortMerge_hash(rawArray, indexLeft, mid, length);
    hashArr += sortMerge_hash(rawArray, mid + 1, indexRight, length);
    while (indexLeftMerge <= mid || indexRightMerge <= indexRight)
    {
        if (indexLeftMerge <= mid && (rawArray[indexLeftMerge] <= rawArray[indexRightMerge]
			|| indexRightMerge > indexRight))
            tmpArray.push_back(rawArray[indexLeftMerge++]),
			tmpFact.push_back(hash_index[indexLeftMerge - 1]);
        else
        {
            tmpArray.push_back(rawArray[indexRightMerge++]),
			tmpFact.push_back(hash_index[indexRightMerge - 1]);
            for (ALL(i, indexLeftMerge, mid))
            {
                hashArr += fact(hash_index[i]); //hash计算
            }
        }
    }
    for (ALL(i, indexLeft, indexRight))
        rawArray[i] = tmpArray[indexTmpArray++],
		hash_index[i] = tmpFact[indexTmpArray - 1]; //补了交换权重【这样可以准确算出每一位的逆序对
    return hashArr;
}

//使用例
int arr[MAX_LENGTH], arr_hash[MAX_LENGTH];
{
    int n;
    scanf("%d", &n);
    for (ALL(i, 1, n))
        scanf("%d", &arr[i]), arr_hash[i] = arr[i];

    printf("Each inversion:\n"); //输出每一位的逆序对个数
    cout << setw(7) << "---Top:";
    for (ALL(i, 1, n))
        cout << setw(7) << i;
    cout << endl
         << setw(7) << "---Num:";
    for (ALL(i, 1, n))
        cout << setw(7) << arr[i];
    cout << endl
         << setw(7) << "";
    for (ALL(i, 1, n))
        cout << setw(8) << "↓";
    cout << endl
         << setw(7) << "---CNT:";
    long long inverSum = sortMerge_inv(arr, 1, n);
    for (ALL(i, 1, n))
        cout << setw(7) << inver[i];
    printf("\nInversions conut: %lld\n", inverSum); //输出逆序对和

    hash_init(n);
    printf("Hash: %lld\n", sortMerge_hash(arr_hash, 1, n, n)); //输出全排列hash值

    printf("Sort: "); //输出归并排序后结果。
    for (ALL(i, 1, n))
        printf("%d ", arr[i]);
}

单调队列

用来求一定范围内的最值。

典型例题为“滑动窗口”

给出一个长度为\(n\)的数组,输出每\(k\)个连续的数中的最大值和最小值。

  • 其中的单调为一种思想:

    当我们解决问题的时候发现有许多冗杂无用的状态时,我们可以采用单调思想,用单调队列或类似于单调队列的方法去除冗杂状态,保存我们想要的状态,

struct Node
{
	int Value, Top;
} Line[1000005];	 //单调队列

int Line_N[1000005], //原数据
	ans[1000005],	 //最终得到的最值,答案数组
	Num,			 //数据个数
	Length;			 //窗口长度

void Push(int Top, int Num, int Tail) //入队操作
{
	Line[Tail].Top = Top;
	Line[Tail].Value = Num;
}
void Find_Min() //寻找最小值
{
	int Head = 1, Tail = 0;
	for (int i = 1; i < Length; i++)
	//这里前m-1个先直接进入队列,因为不用记录前m-1个的最值,只有第m个才能找出最值
	//【假如窗长3,相当于第3个找第1个到第3个内的,第4个找第2个到第4个内的,所以把前2个push进队,从第三个开始找
	{
		while (Head <= Tail && Line_N[i] <= Line[Tail].Value)
			Tail--;
		//维护序列单调,如入队的数小于尾,破坏了单调递增,tail--把尾pop出去,直到大于等于队尾呈递增或者队列空
		Push(i, Line_N[i], ++Tail); //然后入队
	}
	for (int i = Length; i <= Num; i++)
	{
		while (Head <= Tail && Line_N[i] <= Line[Tail].Value)
			Tail--;
		Push(i, Line_N[i], ++Tail); //同上道理,首先,要维护单调性,然后push
		if (Line[Head].Top < i - Length + 1)
			Head++;								//判断出窗没有
		ans[i - Length + 1] = Line[Head].Value; //这个时候第i个窗的最值为队首
	}
}
//最大值只用将有关数据比较的小于等于改为大于等于即可
//使用例
{
	for (ALL(i,1,Num-Length+1)) cout<<ans[i]<<" ";	//直接从头到尾输出答案数组。
}

最小生成树

求出联通整个图所需要的最小边权。

一定会选择\(n-1\)条边。

典型例题为:

我们要在n个城市中建立一个通信网络,则连通这n个城市需要布置n-1一条通信线路,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网?

Kruskal

该算法的基本思想是从小到大加入边,是个贪心算法。

  • 过程:

    1. 按照边权进行排序
    2. 寻找最小边,如果加入后不会形成环,则选择此边。
    3. 重复,直到所有点联通(选择\(n-1\)条边)。
  • 算法点:

    • 并查集(用于判断加入后是否为环)
    • 贪心(排序)
    • 图的存储
  • 用途:

    • 最小生成树
    • 判断整个图是否联通。
#define N 200005

int n, m,
	f[N],	 //并查集数组
	ans,	 //最小边权和
	bs;		 //当前连了几条边
bool pd = 0; //是否联通,联通为1
struct Edge	 //储存方式:按边存
{
	int u, v, w;
} e[N];

int find(int x) //并查集查找
{
	if (f[x] == x)
		return x;
	return f[x] = find(f[x]);
}
bool cmp(Edge x, Edge y) //按权值排序
{
	return x.w < y.w;
}
//初始化
{
	for (register int i = 1; i <= n; i++) //并查集初始化
		f[i] = i;
	sort(e, e + m, cmp);				   //对边排序
}
//Kruskal算法实现
int main()
{
	for (register int i = 0; i < m; i++)
	{
		int fv = find(e[i].v), fu = find(e[i].u); //我们取出当前边的起点和终点所在的祖先
		if (fv == fu)
			continue;  //如果它们相同,就说明它们联通,那么就不用加这条边了
		f[fv] = fu;	   //把祖先存进去
		ans += e[i].w; //总答案+=这条边的权值
		if (++bs == n - 1)
		{			//连通n个点需要n-1条边
			pd = 1; //判断是否连通的东西
			break;
		}
	}

	if (!pd)
		cout << "orz"; //如果不连通就输出(这题好像没有这个数据
	else
		cout << ans;
}

最短路

Dijkstra

  • 过程: 0. 初始化:将所有距离设为\(\inf\),然后把起点设为0,并加入小根堆。

    1. 对那些刚刚被加入第一个集合的结点的所有出边执行松弛操作。
    2. 从第二个集合中,选取一个最短路长度最小的结点,移到第一个集合中。
    3. 重复:直到第二个集合为空,算法结束。
  • 注意点:没有负权。

const int MaxN = 100010, MaxM = 500010;

struct edge //存储方式——邻接表
{
	int to, dis, next;
} e[MaxM];
int head[MaxN]; //邻接表的头指针

int dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;

inline void add_edge(int u, int v, int d)
{
	cnt++;
	e[cnt].dis = d;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

struct node
{
	int dis;
	int pos;
	bool operator<(const node &x) const
	{
		return x.dis < dis;
	}
};

std::priority_queue<node> q;

inline void dijkstra()
{
	dis[s] = 0;
	q.push((node){0, s});	//初始化2——起点
	while (!q.empty())
	{
		node tmp = q.top();
		q.pop();
		int x = tmp.pos, d = tmp.dis;
		if (vis[x])
			continue;
		vis[x] = 1;	//要取出来后,才证明这个是最小dis,才更改vis
		for (int i = head[x]; i; i = e[i].next)	//对所有边松弛
		{
			int y = e[i].to;
			if (dis[y] > dis[x] + e[i].dis)	//松弛操作
			{
				dis[y] = dis[x] + e[i].dis;
				if (!vis[y])	//没被确定,入堆
					q.push((node){dis[y], y});
			}
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; ++i)
		dis[i] = 0x7fffffff; //初始化
	for (register int i = 0; i < m; ++i)	//读边
	{
		register int u, v, d;
		scanf("%d%d%d", &u, &v, &d);
		add_edge(u, v, d);
	}

	dijkstra();

	for (int i = 1; i <= n; i++)
		printf("%d ", dis[i]);
}

拓扑排序

  • 思想:

    1. 选择一个入度为0的顶点输出
    2. 从AOV网删除这个节点,并且将所有与这节点有关的节点入度-1
    3. 重复以上两步,直到不存在入度为0的
    4. 如果输出数少于节点数,即实际上还有节点没输出出来,因此肯定是此图有回路,否则拓扑排序成功
  • 用途:

    1. 按照“在走到一个节点之前,必须把所有能走到它的节点走到”这种条件,对图排序。(类似于要先学前置知识)
    2. 判断是否有环。
int In[105],		//In记录所有节点的入度,
	Out[105][105],	//存储方式——邻接表。
					//Out记录一个节点能走到的节点
					//特别的Out[i][0]为i节点能走到节点的个数(出度)
	Line[105];		//Line存排序结果

void Push(int Top, int &Tail) //入Line队列
{
	Line[++Tail] = Top;
}
void Pop_Push(int Top, int &Head, int &Tail)
{
	cout << Line[Top] << " ";	//先输出这个节点
	Head++;		//删除这个节点,即出队
	for (int i = 1; i <= Out[Line[Top]][0]; i++) //把它所有能走到的节点的入度--
	{
		In[Out[Line[Top]][i]]--;
		if (!In[Out[Line[Top]][i]])
			Push(Out[Line[Top]][i], Tail); 
			//这个时候判断是否为0,如果为0即push入队列里
	}
}

void Topo(int Many) //拓扑
//如果要判断是否有环,即看tail是否小于many即可
{
	int Head = 1, Tail = 0;
	for (int i = 1; i <= Many; i++) 
	//刚开始从头到尾遍历一遍,如果入度为0,push到专门存入度为0的Line队列里
		if (!In[i])
			Push(i, Tail);
	while (Head <= Tail)
		Pop_Push(Head, Head, Tail); //开始排序
}
int main()
{
	int Many, T;
	cin >> Many;	//有多少个节点
	for (int i = 1; i <= Many; i++)
	{
		cin >> T;	//开始读入每个节点的边
		while (T)
		{
			Out[i][++Out[i][0]] = T; //记录能走到的节点
			In[T]++;	//能走到的节点的入度++
			cin >> T;
		}
	}
	Topo(Many);
}
/* 读入:
5
0
4 5 1 0
1 0
5 3 0
3 0
*/
/* 输出:
2 4 5 3 1
*/

KMP

用于“字符串匹配”问题。

  • 什么是字符串的模式匹配?

    给定两个字符串\(S=“s_1,s_2,s_3,\cdots,s_n”\)\(T=“t_1,t_2,t_3,\cdots,t_m"(m \le t)\)
    主串S中寻找子串T的过程叫做模式匹配,T称为模式。

#include <bits/stdc++.h>
#define MAX 2000000
using namespace std;
char s[MAX], f[MAX];
int Next[MAX];
int main()
{
	scanf("%s%s", s, f);
	int lens = strlen(s), lenf = strlen(f), k = 0;
	for (int i = 1; i < lenf; i++)
	{
		while (k && f[i] != f[k])
			k = Next[k];
		Next[i + 1] = f[i] == f[k] ? ++k : 0;
	}
	k = 0;
	for (int i = 0; i < lens; i++)
	{
		while (k && s[i] != f[k])
			k = Next[k];
		k += s[i] == f[k] ? 1 : 0;
		if (k == lenf)
			printf("%d\n", i - lenf + 2);	//输出子串t在主串s中出现的位置
	}
	for (int i = 1; i <= lenf; i++)
		printf("%d ", Next[i]);
}
/* 输入:
ABABABC
ABA
*/
/* 输出:
1
3
0 0 1 
*/
//前面n-1行代表出现的不同位置
//最后一行代表字串t不同长度的border[i]
  • border[i] 记为\(\pi(i)\),代表:字符串\(t\)最长的“相等的真前缀与真后缀”的长度。
    特别地,规定 \(\pi[0]=0\)

举例来说,对于字符串 abcabcd
\(\pi[0]=0\) ,因为 a 没有真前缀和真后缀,根据规定为\(0\)
\(\pi[1]=0\) ,因为 ab 无相等的真前缀和真后缀
\(\pi[2]=0\) ,因为 abc 无相等的真前缀和真后缀
\(\pi[3]=1\) ,因为 abca 只有一对相等的真前缀和真后缀:a,长度为\(1\)
\(\pi[4]=2\) ,因为 abcab 相等的真前缀和真后缀只有ab,长度为\(2\)
\(\pi[5]=3\) ,因为 abcabc 相等的真前缀和真后缀只有abc,长度为\(3\)
\(\pi[6]=0\) ,因为 abcabcd 无相等的真前缀和真后缀

同理可以计算字符串 aabaaab 的前缀函数为 \([0, 1, 0, 1, 2, 2, 3]\)

Manacher

用于求回文串的算法。

给出一个只由小写英文字符\(\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z\)组成的字符串\(S\),求\(S\)中最长回文串的长度。
字符串长度为\(n\)

#include <bits/stdc++.h>
#define N 50000000
#define MaxLen Right - i
#define Mirror 2 * Mid - i
using namespace std;
char s[N << 1];
int RL[N << 1];
void Read()	//对读入的预处理——加入#来分割
{
	int i = 1;
	s[0] = '~', s[1] = '#';
	while ((s[++i] = getchar()) != EOF)
		s[++i] = '#';
}
int Manacher()
{
	int Mid = 2, Right = 3, len = strlen(s) - 3, ans = 0;
	RL[1] = 1, RL[2] = 2;
	for (int i = 3; i <= len; i++)
	{
		if (i < Right)
			RL[i] = min(MaxLen, RL[Mirror]);
		else
			RL[i] = s[i] == '#' ? 1 : 2;
		while (s[i - RL[i]] == s[i + RL[i]])
			RL[i]++;
		if (Right < i + RL[i] - 1)
			Right = i + RL[i] - 1, Mid = i;
		ans = RL[i] - 1 > ans ? RL[i] - 1 : ans;
	}
	return ans;
}
int main()
{
	Read();
	cout << Manacher();
}

字典树——Trie

用于:查找一个字符串是否在“字典”中出现过。

找的封装好的模板。

struct trie
{
	int nex[100000][26], cnt;
	bool exist[100000]; // 该结点结尾的字符串是否存在

	void insert(char *s, int l) // 插入字符串
	{
		int p = 0;
		for (int i = 0; i < l; i++)
		{
			int c = s[i] - 'a';
			if (!nex[p][c])
				nex[p][c] = ++cnt; // 如果没有,就添加结点
			p = nex[p][c];
		}
		exist[p] = 1;
	}
	bool find(char *s, int l) // 查找字符串
	{
		int p = 0;
		for (int i = 0; i < l; i++)
		{
			int c = s[i] - 'a';
			if (!nex[p][c])
				return 0;
			p = nex[p][c];
		}
		return exist[p];
	}
};

其他

快速读入

inline int intRead()
{
	int f=1,num=0;
	char t=getchar();
	while (t<'0' || t>'9') if (t=='-') f=-1,t=getchar(); else t=getchar();
	while (t>='0' && t<='9') num=num*10+t-'0',t=getchar();
	return f*num;
}

#define ALL(NAME_i, BEGIN, TO) \
	int NAME_i = BEGIN;        \
	NAME_i <= TO;              \
	NAME_i++

#ifdef SuperSASS
freopen("data.in", "r", stdin);
#endif