1.啥是KMP算法？ KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。(源自百度百科)2.代码 #include<bits/stdc++.h> using namespace s...
扩展欧几里得算法。 修复了溢出longlong的bug。在int128下也不容易进一步溢出了。求解模n意义下a的逆元，即求方程LCE2(a,1,n,x)，结果放入x中，返回值指示是否有解。 ll gcd(ll a, ll b) {if(b == 0)return a;while(ll t = a % b)a = b, b = t;return b; }ll ex_gcd(ll a, ll b, ll& x, ll& y) {if(b == 0) {x = 1, y = 0;return a;}ll d = ex_gcd(b, a % b, x, y), t;t = x, x = y, y = t - a / b * y;return d; }//解线性同余方程...
对一个大质数进行质因数分解 需要引用miller-robin来判素数 一直写的gcd居然挂掉了... 以后用__gcd了 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define ull unsigned long long #define lb long double ll maxfac;inline ll ksc(ull x,ull y,ll p){//O(1)快速乘（防爆long long）return (x*y-(ull)((lb)x/p*y)*p+p)%p; }ll pow_mod(ll x, ll y, ll mod) {ll res = 1;while(y) {if(y & 1) res = ksc...
void add_dinic(int u, int v) {e[++cnt].v = v;e[cnt].w = 0;e[cnt].nxt = head[u];head[u] = cnt; }int dfs_dinic(int x, int flow) {if (x == ed) return flow;int res = 0;for (int i = now[x]; i != -1; i = e[i].nxt){int v = e[i].v;if (d[v] + 1 == d[x] && e[i].w > 0){int k = dfs_dinic(v, min(e[i].w, flow));res += k;flow -= k;e[i].w -= k;e[i ^ 1].w += k;if (!flow) break;}}return res; }bool bfs_dinic() {mems...
捕获类错误并让错误消息从类“冒泡”到视图并最终显示在模板上的正确方法是什么？ 我现在遇到的问题是,我最终在模型和视图控制器中两次捕获相同的错误.这感觉不对. 这是一个例子： 型号/user.pyclass User(object):errors = []def __init__(self, string=None):""" Initialize the user object"""#See if the input string is an e-mail addresstry:string_is_email = string.index('@')except ValueError:self.errors.append('Inv...
BFS算法整理(python实现） 广度优先算法（Breadth-First-Search），简称BFS，是一种图形搜索演算算法。 1. 算法的应用场景 2. 算法的模板 2.1 针对树的BFS模板无需分层遍历from collections import deque# Definition for a binary tree node. class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef level_order_tree(root, result):if not root:return# 这里借助python的双向队列实现队列# 避免...
#include<bits/stdc++.h> using namespace std; typedef long long ll;inline int gcd(int a,int b){if(!b)return a;else{while(int i=a%b){a=b;b=i;}return b;} }inline int qpow(ll a,int n,int m) {//这个快速幂保证p不是1，少模一次是一次ll s=1;while(n) {if(n&1)s=s*a%m;a=a*a%m;n>>=1;}return s; }unordered_map<int,int> M; //要求a,n互质 a^x=b mod n .k,t是留给exbsgs调用的 int bsgs(int a,int b,int n,int k=1,int t=0...
inline int gcd(int a,int b){if(b==0)return a;else{while(int i=a%b){a=b;b=i;}return b;} }int ex_gcd(int a,int b,int& x,int& y) {if(b==0) {x=1;y=0;return a;}int d=ex_gcd(b,a%b,x,y);int temp=x;x=y;y=temp-a/b*y;return d; }//解线性同余方程 ax + by = c bool _LCE(int a, int b, int c, int &x0, int &y0) {int x,y;int d=ex_gcd(a,b,x,y);if(c%d!=0){//无解return 0;}//ax0 + by0 = gcd(a,b)int k=c/d;x0=x*k;y0=y*k;...
原文链接：bestsort.cn原文地址：bestsort.cn int cnt[MAXn]; char String[MAXn]; void Manacher(char s[],int len) {//原字符串和串长int l = 0;String[l++] = '$'; // 0下标存储为其他字符,防止越界String[l++] = '#';for (int i = 0; i < len; i++) {String[l++] = s[i];String[l++] = '#';}String[l] = 0; // 空字符int MaxR = 0;int flag = 0;for (int i = 0; i < l; i++) {cnt[i] = MaxR > i ? min(cnt[2 * flag - i], MaxR ...
KMP算法 KMP算法指的是字符串模式匹配算法，问题是：在主串T中找到第一次出现完整子串P时的起始位置。该算法是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，以其名字首字母命名。 下面是KMP算法的C++版本： #include <iostream> #include <string> #include <vector>using namespace std; //getNext vector<int> getNext(string str2) {if (str2.length() == 1) {vector<int> next{ -1 };return next;}vector<int> nex...
#include<bits/stdc++.h> using namespace std;#define go(i,a,b) for(int i=a;i<=b;++i) #define com(i,a,b) for(int i=a;i>=b;--i) #define mem(a,b) memset(a,b,sizeof(a))const int inf=0x3f3f3f3f,N=1000+10;int n1,n2,m,vis[2*N],head[N<<1],match[N<<1],cnt=0; struct edge{int nxt,v; }e[N*N*2];void add(int u,int v){e[cnt]=(edge){head[u],v};head[u]=cnt++; }bool dfs(int u){for(int i=head[u];i+1;i=e[i].nxt){int v...
Swap< T,Position1,Position2,Pack> :: type,其中Pack由类型T的元素组成,是返回包含Position1和Position2中的元素的包.我的解决方案不是最有效的.应该有一种方法可以非常干净地完成这项任务,而无需两次访问任何元素.有人能想到吗？// ReplaceElement replaces the element of a pack with a specified position (0 being the first position) with a specified value. template <typename T, std::size_t, std::size_t, T, typenam...
BSGS （大步小步算法） 已知\(a、b、 c\)，求\(x\)。令\(a^x \equiv b \pmod c\)。 步骤 \[m = \lceil \sqrtｃ\ \rceil \]\[x = i*m-j\ \ (i\in[1, m], j\in[0, m])\]\[a^{i*m-j} \equiv b \pmod c\]\[a^{i*m}\equiv b*a^j \pmod c\] 枚举\(a^j(j\in[0, m])\)放入\(hash\)表里面，再枚举\(a^{i*m}\)，在\(hash\)表里面找有没有相同，如若有相同的那么就存在。 如果在询问较多的情况下，可以把\(bm = \lceil c^{\frac{2}{3}}\rceil...
const int maxn=1e4+10; int nex[maxn];//记录的是前缀和后缀最大公共部分的下一位坐标，由数组前后缀最大公共长度右移一位得出 char p[maxn],s[maxn]; void init() {fill(nex,nex+maxn,0);//fill(p,p+maxn,''); } void getnex() {int i=-1,j=0;//因为求next数组是由前缀和后缀共同求出，切next[1]没求出，所以i要从-1开始，j从零开始 nex[0]=-1;int len=strlen(p);while(j<len-1){//i=-1表示不存在公共前缀和后缀 if(i==-1||p[i]...
Dijkstra算法 分析 Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路（ Single-Source Shortest Paths， SSSP） ， 即从单个源点出发， 到所有结点的最短路（这样最后返回你想要的那个节点对应的距离即可）。 该算法同时适用于有向图和无向图。 其伪代码如下： 清除所有点的标号 设d[0]=0， 其他d[i]=INF //INF被定义为一个很大的数字 循环n次 { 在所有未标号结点中， 选出d值最小的结点x 给结点x标记...