一些杂项算法
2022/8/11 14:25:35
本文主要是介绍一些杂项算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
KMP
代码实现
时间复杂度\(O(n + m)\)
int n, m; int next[M + 1], f[N + 1]; char s[N + 2], p[M + 2]; void kmp() { n = strlen(s + 1), m = strlen(p + 1); int j = 0; nxt[1] = 0; for (int i = 2; i <= m; i++) { while (j > 0 && p[j + 1] != p[i]) j = nxt[i]; if (p[i + 1] == p[i]) j++; nxt[i] = j; } j = 0; for (int i = 1; i <= n; i++) { while ((j == m) || (j > 0 && p[j + 1] != s[i])) j = nxt[j]; if (p[j + 1] == s[i]) j++; f[i] = j; } } /* 简化写法 两个字符串拼接起来用#分割 int n = strlen(s+1), m = strlen(p+1); p[m + 1] = '#'; for (int i = 1, j = m + 2; i <= n; i++, j++) p[j] = s[i]; int j = 0; nxt[1] = 0; for (int i = 2; i <= n + m + 1; i++) { while (j && p[i] != p[j + 1]) j = nxt[j]; if (p[i] == p[j + 1]) j++; nxt[i] = j; } */
exkmp
代码实现
时间复杂度\(O(n)\)
void exkmp() { int L = 1, R = 0; z[1] = 0; for (int i = 2; i <= n; i++) { if (l > R) z[i] = 0; else { int k = i - L + 1; z[i] = min(z[k], R - i + 1); } while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) z++; if (i + z[i] - 1 > R) L = i, R = i + z[i] - 1; } }
快速幂
代码实现
时间复杂度\(O(logn)\)
long long qp(long long a, int n) { long long ans = 1; for (; n; n >>= 1) { if (n & 1) ans *= a, ans %= p; a *= a, a %= p; } }
快速乘
代码实现
用于快速计算 \(a \times b \pmod p\)
当 \(0 \le a,b\le10^9,1\le P\le10^9\)时,可以直接计算
当 \(0 \le a,b\le10^{18},1\le P\le10^9\)时,可以\((a\%p \times b\%p)\%p\)进行计算
当 \(0 \le a,b\le10^{18},1\le P\le10^{18}\)时,需要用到快速乘
时间复杂度\(O(logn)\)
long long qm(long long a, long long b, long long p) { long long ans = 0; a %= p;//重要 for (; b; b >>= 1) { if (b & 1) ans += a, ans %= p; a += a; a %= p; } return ans; }
矩阵乘法
代码实现
设A是一个n行m列的矩阵,B是一个m行k列的矩阵,矩阵\(C=A\times B\)
计算方式:\(C_{i,j}=\sum_{k=1}^mA_{i,j}B_{k,j}\)
A的列数等于B的行数才可以进行矩阵乘法
const int K = 200, P = 1e9 + 7; int n; long long a[N + 1][N + 1], f[N + 1]; void aa() { long long w[N + 1][N + 1]; memset(w, 0, sizeof(w)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) w[i][j] += a[i][k] * a[k][j], w[i][j] %= p; memcpy(a, w, sizeof(a)); } void fa() { long long w[N + 1]; memset(w, 0, sizeof(w)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) w[i] += f[i] * a[j][i], w[i] %= p; memcpy(f, w, sizeof(f)); } void matrixpow(int k) { for (; k; k /= 2) { if (k & 1) fa(); aa(); } }
这篇关于一些杂项算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解