22.1.22 并查集和KMP算法
2024-08-31 18:59:33
22.1.22 并查集和KMP算法
1.并查集结构
1)实现:
并查集有多种实现方式,例如向上指的图的方式,数组的方式等等。其根本思想就在于准确记录某个节点的根节点,这个这种记录就能够很快的实现并查集的两种主要的功能:合并和查询。
2)两种优化方法:
压缩路径;
在合并时将深度小的树合并到深度大的树。
3)code:
public static class PointUnion<V>
{
private V value;
public PointUnion(V value)
{
this.value = value;
}
}
public static class UnionSet<V>
{
public HashMap<V,PointUnion<V>> PUmap ;
public HashMap<PointUnion<V>,PointUnion<V>> Fathermap ;
public HashMap<PointUnion<V>,Integer> Rankmap ;
public UnionSet(List<V> list)
{
PUmap = new HashMap<V,PointUnion<V>>();
Fathermap = new HashMap<PointUnion<V>,PointUnion<V>>();
Rankmap = new HashMap<PointUnion<V>,Integer>();
for(V value : list)
{
PointUnion<V> PU = new PointUnion<V>(value);
PUmap.put(value, PU);
Fathermap.put(PU, PU);
Rankmap.put(PU, 1);
}
}
public PointUnion<V> FindFather(PointUnion<V> PU)
{
Stack<PointUnion<V>> S = new Stack();
while(PU!=Fathermap.get(PU))
{
S.push(PU);
PU = Fathermap.get(PU);
}
while(!S.isEmpty())
{
Fathermap.put(S.pop(), PU);
}
return PU;
}
public boolean isSameUnion(V a, V b)
{
if(PUmap.containsKey(a)&&PUmap.containsKey(b)&&FindFather(PUmap.get(a))==FindFather(PUmap.get(b)))
return true;
return false;
}
public void union(V a, V b)
{
if (PUmap.containsKey(a) && PUmap.containsKey(b))
{
PointUnion<V> aF = FindFather(PUmap.get(a));
PointUnion<V> bF = FindFather(PUmap.get(b));
if (aF != bF)
{
PointUnion<V> big = Rankmap.get(aF) >= Rankmap.get(bF) ? aF : bF;
PointUnion<V> small = big == aF ? bF : aF;
Fathermap.put(small, big);
Rankmap.put(big, Rankmap.get(aF) + Rankmap.get(bF));
Rankmap.remove(small);
}
}
}
}
2.KMP算法
1)用途:
KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。
例如有这样的一个问题:判断一个较短的字符串是否为一个较长的字符串的子串。
我们很容易想到这样的一种方法:从较长的字符串的第一位开始与较短的字符串比较,相同则同时后移,不同的话较长的字符串从第二位开始再与较短的字符串的第一位比较,重复之前的步骤,直到找到或者遍历完较长的字符串。
第二种高效的方法:KMP算法
2)解释:
code:
public static int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
int i1 = 0;
int i2 = 0;
int[] next = getNextArray(str2);
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] == -1) {
i1++;
} else {
i2 = next[i2];
}
}
return i2 == str2.length ? i1 - i2 : -1;
}
public static int[] getNextArray(char[] ms) {
if (ms.length == 1) {
return new int[] { -1 };
}
int[] next = new int[ms.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i < next.length) {
if (ms[i - 1] == ms[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
public static void main(String[] args) {
String str = "abcabcababaccc";
String match = "ababa";
System.out.println(getIndexOf(str, match));
}
最新文章
- Ceph RGW服务 使用s3 java sdk 分片文件上传API 报‘SignatureDoesNotMatch’ 异常的定位及规避方案
- js 倒计时
- iOS---FMDB数据升级
- 【OpenGL】VAO与VBO
- Codeforces Round #379 (Div. 2) C. Anton and Making Potions 枚举+二分
- java输入函数
- Spring MVC 之文件上传(七)
- 解决:mvn archetype:create Abstract class or interface &#39;org.apache.maven.artifact.repository.ArtifactRepository&#39; cannot be instantiated
- HTML 段落
- [转]后缀自动机(SAM)
- 可视化Windows服务定时任务
- Android Wear开发 - 入门指引 - Eclipse开发平台搭建
- HBase笔记--filter的使用
- Installing on CentOS/RHEL / KB forum / Ajenti
- gitlab自动备份
- treeview树(利用数据表实现)带展开
- FFmpeg and x264 Encoding Guide
- 关于css盒模型
- ASP.NET Core 四种方式绑定枚举值
- SpringMVC用到的jar包