并查集
支持集合快速合并
所有数据生成各自的集合,需要提供查询两个两素是不是属于一个集合,和集合合并操作,并查集能够在常数时间级别上对两个操作进行实现
1. 构造结构(数据+指针),将自己的指针指向自己,在查询操作时,只需要沿着指针走到头,看是否是一个元素,在合并操作时,另一个元素的指针指向需要合并的另一个元素(尺寸少的顶部挂在尺寸多的顶部下即可)
2. 在某次查找顶部节点时,将沿途节点的指针都直接指向顶部节点
3. 指针指向可以使用一个哈希表进行实现 elementmap fathermap sizemap(仅有顶部元素有记录)
KMP(字符串匹配加速算法)
有两个字符串str1、str2,查看str2是不是str1的子串
最长前缀(前缀和后缀的最大匹配长度):假设某个字符的之前的字符为abbabb,那么其最长前缀为abb,长度为3
假设str2为aabaabsa,那么根据其最长前缀信息作为其对应的next数组=[-1 0 1 0 1 2 3 0]
KMP流程:
1. 如果字符出现了不匹配,使用str2当前不匹配字符对应的next信息,将next对应字符移到当前不匹配位置进行比较
2. 如果str2移到第一个字符还是不能与srr1目前比对位置匹配,及next=-1时,将str1比对位置右移一位
求解next数组:
1. 0位置规定为-1,1位置规定为0
2. i位置是,利用i-1位的信息,如果next[i-1]=7,如果i-1的字符与第八个字符相同,next[i] = 8。如果不一样,就继续往前跳(利用第八个字符的next信息)
例题:
13 · 字符串查找 - LintCodehttps://www.lintcode.com/problem/13/?showListFe=true&page=1&submissionStatus=ACCEPTED&pageSize=50
class Solution {
public:vector<int> nexts;void cal_next(string str){if(str.size()==1){nexts.push_back(-1);return;}nexts.push_back(-1);nexts.push_back(0);int i = 2;int cn = 0;while(i < str.size()){if(str[i-1]==str[cn]){nexts.push_back(cn+1);cn++;i++;}else if(cn>0){cn = nexts[cn];}else{nexts.push_back(0);i++;}}}int strStr(string &source, string &target) {int len1 = source.size();int len2 = target.size();if(len2>len1)return -1;cal_next(target);int pos1 = 0 , pos2 = 0;while(pos1<len1&&pos2<len2){if(source[pos1]==target[pos2]){pos1++;pos2++;}else if(pos2>0){pos2 = nexts[pos2];}else{pos1++;}}return pos2==len2?pos1-pos2:-1;}
};