c++算法题模板

### C++ 算法题目模板代码示例 #### 排序算法 对于排序问题，可以采用多种方法实现。以下是冒泡排序的一个简单例子： ```cpp void BubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } } ``` 此段代码实现了基本的冒泡排序逻辑[^1]。 #### 字符串匹配算法 当涉及到字符串匹配时，暴力求解是一种直观的方法。下面是一个简单的暴力匹配程序片段： ```cpp #include <iostream> using namespace std; int main() { int n, m; string s, p; // s为较长字符串（模式串） cin >> n >> p >> m >> s; for (int i = 0; i < m; i++) { bool flag = true; // 最开始是匹配成功的状态 for (int j = 0; j < n; j++) { if (s[i + j] != p[j]) { flag = false; // 只要有一个不通过，则设置为false并跳出循环 break; } } if (flag == true) { cout << i << " "; } } return 0; } ``` 这段代码展示了如何利用双重循环来逐字符比较两个字符串，并输出所有可能的位置索引[^2]。 #### KMP算法中的next数组处理部分 在更高效的KMP算法中，`next[]` 数组用于记录前缀函数值，从而加速模式串与目标串之间的匹配过程。这里给出了一段更新 `j` 的关键语句： ```cpp while(j >= 0 && s[i] != t[j + 1]) { j = next[j]; } ``` 该行代码的作用是在发生失配的情况下调整指针位置以便继续尝试其他潜在匹配点[^3]。 #### 快速幂运算及其应用——费马小定理求逆元 快速幂运算是计算大数次方的有效手段之一，在模意义下尤其有用。下面是基于二分思想优化后的快速幂函数定义以及其应用于求取乘法逆元的具体实例： ```cpp // 计算(a^b)%c的结果 int qpow(int a, int b, int c){ int res = 1; while(b){ if(b & 1) res = res * a % c; b >>= 1; a = a * a % c; } return res; } // 使用费马小定理求得a关于mod的乘法逆元 inline long long inv(long long base,long long mod){ return qpow(base,mod-2,mod); } ``` 上述代码不仅提供了快速幂的基础框架，还演示了怎样借助于费马小定理高效地找到特定条件下存在的乘法逆元[^4]。