达州做网站
大橙子网站建设，新征程启航
为企业提供网站建设、域名注册、服务器等服务
预备役间学习记录9-创新互联
一、学习算法
1、字符串
（1）kmp(字符串比配)
分享标题：预备役间学习记录9-创新互联
转载源于：http://dzwzjz.com/article/djegji.html
主要运用到（第0位-1)从第二位开始对每位的前字符串求大前缀和后缀的相同子串长度；
创新互联公司网站建设公司一直秉承“诚信做人，踏实做事”的原则，不欺瞒客户，是我们最起码的底线！ 以服务为基础，以质量求生存，以技术求发展，成交一个客户多一个朋友！专注中小微企业官网定制，成都网站设计、网站建设，塑造企业网络形象打造互联网企业效应。
方法：
列如：主串：a b a a c a b a b c a c
子串：a b a b c
next : -1 0 0 1 2
下标 值 串
0 0 空
1 0 a b
2 1 a b a
3 2 a b a b
4 0 a b a b c
next[i]的值为：0--i构成的字符串中出现首尾相同的字串的大长度；
当无首尾相同的子串时next[i]的值为0；
在主串i++和子串j++比较过程中当不一样时，j=next[j];
就像这种第一次不同时i=3,j=3,执行后j=2；
i
a b a a c a b a b c a c
a b a b c
j
往后执行第二次不同i=4,j=3,不同j=next[j],j=2;
i
a b a a c a b a b c a c
a b a b c
j
往后执行第三次不同i=4,j=2,不同j=next[j],j=1;
i
a b a a c a b a b c a c
a b a b c
j
往后执行第四次不同i=4,j=1,不同j=next[j],j=0
i
a b a a c a b a b c a c
a b a b c
j
往后执行第五次不同i=4,j=0，此时注意是在j=0情况下不同，就这样执行i++，j=0;
i
a b a a c a b a b c a c
a b a b c
j
往后执行子串结束，代表比配成功，有这个子串结束循环；
附代码（next数组求法；kmp匹配方法）
#includeusing namespace std;
int net[1001000];
char z[1001000];
char f[1001000];
int j,zc,fc;
main()
{
cin>>z+1;
cin>>f+1;
zc=strlen(z+1);
fc=strlen(f+1);
for(int i=2;i<=fc;i++)
{while(j&&f[i]!=f[j+1])j=net[j];
if(f[j+1]==f[i])j++;
net[i]=j;
}
j=0;
for(int i=1;i<=zc;i++)
{while(j>0&&f[j+1]!=z[i])j=net[j];
if (f[j+1]==z[i]) j++;
if (j==fc) {cout< ## 题目背景
$A$地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
## 题目描述
给出A地区的村庄数$N$，和公路数$M$，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
## 输入格式
第$1$行两个正整数$N,M$
下面$M$行，每行$3$个正整数$x, y, t$，告诉你这条公路连着$x,y$两个村庄，在时间t时能修复完成这条公路。
## 输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出$-1$，否则输出最早什么时候任意两个村庄能够通车。
## 样例 #1
### 样例输入 #1
```
4 4
1 2 6
1 3 4
1 4 5
4 2 3
```
### 样例输出 #1
```
5
```
## 提示
$N \le 1000,M \le 100000$
$x \le N,y \le N,t \le 100000$
并查集，我们定义一个结构体数组来存村庄关系，和之间的时间，定义一个数组记录集合；
按时间从小到大对结构体数组排序；
之后，对结构体从i=1;i<=n;i++开始检索，并进行并查，到查到所有村庄都到一个集合时，此时检索到的关系时间就是最短时间，如果i>n还没到一个集合则输出-1
附代码
#include#include
using namespace std;
struct jh
{int x;
int y;
int t;
}zj[100000];
int jl[100000];
int bj(const jh &a,const jh &b){return a.t>n>>m;
for(int i=0;i>zj[i].x>>zj[i].y>>zj[i].t;if(zj[i].x>maxx)maxx=zj[i].x;if(zj[i].y>maxx)maxx=zj[i].y;}
sort(zj,zj+m,bj);
if(n==1){cout<<0;k=2;}
else
for(int i=0;imaxt){maxt=zj[i].t;}
if(jl[zj[i].x]==0&&jl[zj[i].y]==0)
{jl[zj[i].x]=jl[zj[i].y]=i+1;}
else
if(jl[zj[i].x]!=0&&jl[zj[i].y]==0)
{jl[zj[i].y]=jl[zj[i].x];}
else
if(jl[zj[i].x]==0&&jl[zj[i].y]!=0)
{jl[zj[i].x]=jl[zj[i].y];}
else
{int z=jl[zj[i].x];
int x=jl[zj[i].y];
for(int i=0;i<=maxx;i++)
if(jl[i]==z)jl[i]=x;
}
int j,js=1;
for(j=2;j<=maxx;j++)
{if(jl[j]!=jl[1]||jl[1]==0)break;else js++;}
if(js==n&&jl[1]!=0){cout< ## 题目描述
有一个 $n(n \le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 `0 0`。
建好这棵二叉树之后，请求出它的深度。二叉树的**深度**是指从根节点到叶子结点时，最多经过了几层。
## 输入格式
第一行一个整数 $n$，表示结点数。
之后 $n$ 行，第 $i$ 行两个整数 $l$、$r$，分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点，$r=0$ 同理。
## 输出格式
一个整数，表示大结点深度。
## 样例 #1
### 样例输入 #1
```
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
```
### 样例输出 #1
```
4
```
这题考二叉树的遍历计算深度，我们只需定义一个结构体数组来记录每个节点的两个子节点；
然后进行DFS递归，传（1，1）上去代表从第一个节点的左右节点开始；
递归前判断是否到叶子节点0 0，是就直接return；没有到就记深度的变量++，然后先左节点dfs(传左节点的值，层数+1),在右节点dfs（）；
附代码
#include#include
using namespace std;
struct tree
{int z;
int y;
}jl[1000010];
int max1,n;
void zhao(int jd,int cs)
{if(jl[jd].z==0&&jl[jd].y==0)
{max1=max1>n;
for(int i=1;i<=n;i++)
{cin>>jl[i].z>>jl[i].y;}
zhao(1,1);
cout< 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享标题：预备役间学习记录9-创新互联
转载源于：http://dzwzjz.com/article/djegji.html