扩展KMP

优质博客推荐

问题描述:母串S,子串T,求S[i]~S[n-1] (0<=i<n) ,与T的最长公共前缀extend[i]。

求解需要next数组辅助,next[i]表示next[i]~next[m-1]与next[0]~next[m-1]的最长公共前缀。

我们直接讨论在中间时匹配的情况。

已知:

1.假如我们extend已经求到了k,该求k+1了。

2.位置p代表extend[0,k]能匹配到的最远的位置,并且设取这个最大值的位置为po。

3.next数组已知,next[k+1]=len。

求extend数组

一。k+len&[……]

Read more

LCA倍增

优质博客推荐

hdu6115

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int inf=0x3f3f3f3f;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=100005;
int n,m;
int vis[m[......]

Read more

读文章代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ofstream file;
    file.open("yuyin.txt");
    string s;
    char bd='"';
    while(cin>>s)
    {
        if(s[0]==s[1]&&s[1]=='0') break;
        int len=s.size();
        for(int i=0;i<len;i++)[......]

Read more

tarjan之双连通图(无向图)

这里有几个点需要注意
1.为什么无向图缩点需要变成有向图缩点?
无向图两两之间的点可以到达,无法跑回边的话,就跑不到父节点以上的节点了,那么肯定是桥了。
2.为什么不能跑回边,而不是跑父节点?
本来是个无向图单连通,但是你阻止了父节点跑回去,那就不是无向图单连通了。
但是这个题去重也对,嗯。。。数据弱

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,[......]

Read more

tarjan算法之桥

博客推荐

与割点的最大不同之处:low[v]>low[u]

易错点:

1.父亲节点与子节点区别一下,防止两个点误认为环。

2.去重边

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const[......]

Read more

tarjan算法之无向图求割点

先学tarjan算法,再学割点,优质博客 .

割点也就是把此点去掉后,使无向强连通图至少变成2部分。

1.哪些点是割点?

2.此割点把图割成了几部分?

第一个问题:1.如果根有两个或两个以上的树,那么此点必为割点。

2.如果u不是根节点,它有一个子节点v,并且以v为根节点的子树中,没有一个顶点有通向任意一个u的祖先的回边。

第二个问题:就是去点此割点,然后求并查集。

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream&[......]

Read more

tarjan算法之有向图缩点

1.求至少选几个点作为起点走遍全图(也就是这几个点走的路加起来走遍全图)?

2.求最小加多少边能使图变成强连通图?

tarjan缩点求入度为0的点为第一个题的答案,求max(入度为0的点,出度为0的点)为第二个题的答案。

tarjan缩点方法最后给出代码。

疑问:

1.缩点之后的入度为0的点数量为什么为第一问的答案?

入度为0,也就是没有点能够到达它,它也就是起点。但是入度不为0的点,总有点能够到达它。

2.为什么max(入度为0的点,出度为0点)为第二问的答案?

想让此图变成强连通图,就要消除起点和终点,那么就要取他们的最大值。

&nbs[……]

Read more

tarjan算法之有向图求连通分量

过程我就不多说了,百度一下,一堆博客。

我参照kuangbin的板子和hdu1269学的基础。

只会敲板子是非常不开心的,所以我自己想了想过程为什么这样写,以下纯属个人理解,如果有错,欢迎指出。

1.我就想为什么在一个连通内只有一个节点dfn[i]==low[i]?

借鉴此博客理解

答:由于位于同一个连通内,所以任意两个节点可以相互到达,那么两者的low值一定会被另一个所影响(要看谁的low最小),所以不可能存在两对dfn和low的值相等。但是一个连通图内的low值不一定都相等。

2.为什么low值要取最小的,最大的不可以吗?

答:对于一个连通图,我们[……]

Read more