KMP（O(N)）
流程
- 定义两个变量x,y分别表示在原始串str中的位置和匹配串match中的位置。
- 先生成需要匹配的字符串的next数组，next数组记录了当前元素的最长匹配前缀的和后缀的长度，并且也表示如果某一次没有匹配上，那么y需要跳到的位置(最长前缀的下一个元素就是需要继续比较的下一个位置)。
- 同时比较x,y位置的字符是否相等：
1.若相等则x,y同时加一向后继续比较。
2.若不相等，判断此时该位置的next[y]位置是否是还能跳过去的位置如果是-1则表示此时位置已经是match的其实位置，不能再往前跳了，则让x向后走一步，继续和match的0位置开始比较，重复上面过程。若不等于-1表示可以继续跳，用next[y]位置和x位置进行比较若相等重复1，不相等重复2.
两个实质：
- 利用y位置的前缀和数组可以减少不用让x回到当时起点的下一，y回到0位置继续进行比较。(证明在原始串str中后缀的头位置的前一个位置以前不可能在匹配出match字符串)。
- 利用前缀后缀加速
-
/**
* 假设字符串str长度为N，字符串match长度为M，M <= N
* 想确定str中是否有某个子串是等于match的。
* 时间复杂度O(N)
*/
public class Kmp {
// 输入两个字符串str和match，返回match在str中匹配开始的位置，如果不匹配则返回-1
public static int kpm(String str,String match){
if(str == null
|| match == null
|| match.length() == 0
|| str.length() == 0
||str.length() < match.length()){
return -1;
}
char[] strA = str.toCharArray();
char[] matchA = match.toCharArray();
// 定义两个变量一个代表str的下标，一个代表match的下标
// str下标
int x = 0;
// match下标
int y = 0;
// 获取next数组
int[] next = getNextArr(match);
// 只要小标不越界就一直比较
while (x < str.length() && y < match.length()){
if(strA[x] == matchA[y]){
// 如果两个字符相等，继续下一个的比较
x ++;
y ++;
}else if(next[y] == -1){
// 如果此时两个字符不相等，那么需要跳到match的最长前缀的下一个继续进行比较
// 但是此时已经第一元素了，没有最长前缀了，那么y边让str中的x跳到下一个
x ++;
}else {
// 当前位置y 有可以跳的最长前缀的下一个元素
y = next[y];
}
}
// 跳出循环的可能：1.x越界了，但是y没有越界，匹配失败；2.x没有越界但是y越界了，匹配上了；3.x,y同时都越界了匹配上了
// 综上，只要是y越界的都是匹配上的
return y == match.length() ? x - y : -1;
}
// 获取字符串的最长前缀和最长后缀的长度
// match[i]表示在0~i-1上，以字符结尾的子串的最长前缀后最长后缀的长度
// 且也可以代表最长前缀的下一个字符的位置，KMP中如果不满足要求需要跳的位置
private static int[] getNextArr(String match){
// 认为规定 如果只有一个字符那么next[0] = -1;
// 如果多余一个字符那么第二个字符next[1] = 0;
if(match.length() == 1){
return new int[]{-1};
}
char[] matchA = match.toCharArray();
int len = matchA.length;
int[] next = new int[len];
next[0] = -1;
next[1] = 0;
int index = 2;
// 记录index - 1 前一个位置的值，也是index - 1前缀和的下一个位置的坐标
int cn = 0;
// 从第三个字符开始遍历
while (index < len){
// 看当前位置的前一个位置也就是index - 1的位置的值num
// 比较next[num] 和 index - 1是否相等
// 若相等，那么next[index] = next[index - 1] + 1;
if(matchA[index - 1] == matchA[cn]){
// cn index - 1 位置时的最长前缀
// 现在index 跳到下一个了，那就是求index + 1 位置的值
// 所以现在的cn = cn + 1;
next[index ++] = ++cn;
}else if(next[cn] == -1){
// 已经不能在跳了那就是没有
next[index ++ ] = 0;
// 到了这个不那么坑定已经来到了数组中的0位置，那么此时cn =0;
// 此时index = 2 所以下面这句可以不要
cn = next[index - 1];
}else{
// 还能继续跳
cn = next[cn];
}
}
return next;
}
public static void main(String[] args) {
String str = "rabdcadf";
String match = "a";
System.out.println(kpm(str, match));
}
}
例题
- 给你两个字符串str1,str2判断他们是否互为旋转词。旋转词，如字符"abcdef","cdefab"互为旋转词。
流程，用两个str1拼接成一个新的字符串str3，判断str2是否是str3的子串，如果是那么str1,str2互为旋转词，否则不是。
public class XuanZhuanCi {
public static boolean xuanZhuanCi(String str1,String str2){
if(str1 == null || str2 == null || (str1.length() != str2.length())){
return false;
}
String str3 = str1+str1;
// 调用kmp算法
int kpm = Kmp.kpm(str3, str2);
return kpm == -1 ? false : true;
}
public static void main(String[] args) {
String str1 = "abcdef";
String str2 = "cdefab";
System.out.println(xuanZhuanCi(str1,str2));
}
}
- 给定两棵二叉树的头节点head1和head2,想知道head1中是否有某个子树的结构和head2完全一样。
流程：head1,head2两颗二叉树先序序列化，通过kmp看head2序列化后是否为head1的子串，若是，head2是head1的子结构。
/**
* 给定两棵二叉树的头节点head1和head2
* 想知道head1中是否有某个子树的结构和head2完全一样
*/
public class SubTree {
public static boolean subTree(Node head1,Node head2){
if(head1 == null && head2 != null){
return false;
}
if(head1 != null && head2 == null){
return false;
}
if(head1 == null && head2 == null){
return true;
}
// 先序序列化head1 head2
List<String> head1Str = new ArrayList<>();
List<String> head2Str = new ArrayList<>();
pre(head1,head1Str);
pre(head2,head2Str);
return kpm(head1Str,head2Str) != -1;
}
private static void pre(Node head,List<String> list){
if(head == null){
list.add(null);
}else{
list.add(head.value+"");
pre(head.left,list);
pre(head.right,list);
}
}
// 输入两个字符串str和match，返回match在str中匹配开始的位置，如果不匹配则返回-1
public static int kpm(List<String> str,List<String> match){
if(str == null
|| match == null
|| match.size() == 0
|| str.size() == 0
||str.size() < match.size()){
return -1;
}
String[] strA = new String[str.size()];
for (int i = 0; i < strA.length; i++) {
strA[i] = str.get(i);
}
String[] matchA = new String[match.size()];
for (int i = 0; i < matchA.length; i++) {
matchA[i] = match.get(i);
}
// 定义两个变量一个代表str的下标，一个代表match的下标
// str下标
int x = 0;
// match下标
int y = 0;
// 获取next数组
int[] next = getNextArr(matchA);
// 只要小标不越界就一直比较
while (x < str.size() && y < match.size()){
if(isEqual(strA[x],matchA[y])){
// 如果两个字符相等，继续下一个的比较
x ++;
y ++;
}else if(next[y] == -1){
// 如果此时两个字符不相等，那么需要跳到match的最长前缀的下一个继续进行比较
// 但是此时已经第一元素了，没有最长前缀了，那么y边让str中的x跳到下一个
x ++;
}else {
// 当前位置y 有可以跳的最长前缀的下一个元素
y = next[y];
}
}
// 跳出循环的可能：1.x越界了，但是y没有越界，匹配失败；2.x没有越界但是y越界了，匹配上了；3.x,y同时都越界了匹配上了
// 综上，只要是y越界的都是匹配上的
return y == match.size() ? x - y : -1;
}
// 获取字符串的最长前缀和最长后缀的长度
// match[i]表示在0~i-1上，以字符结尾的子串的最长前缀后最长后缀的长度
// 且也可以代表最长前缀的下一个字符的位置，KMP中如果不满足要求需要跳的位置
private static int[] getNextArr(String[] matchA){
// 认为规定 如果只有一个字符那么next[0] = -1;
// 如果多余一个字符那么第二个字符next[1] = 0;
if(matchA.length == 1){
return new int[]{-1};
}
int len = matchA.length;
int[] next = new int[len];
next[0] = -1;
next[1] = 0;
int index = 2;
// 记录index - 1 前一个位置的值，也是index - 1前缀和的下一个位置的坐标
int cn = 0;
// 从第三个字符开始遍历
while (index < len){
// 看当前位置的前一个位置也就是index - 1的位置的值num
// 比较next[num] 和 index - 1是否相等
// 若相等，那么next[index] = next[index - 1] + 1;
if(isEqual(matchA[index - 1],matchA[cn])){
// cn index - 1 位置时的最长前缀
// 现在index 跳到下一个了，那就是求index + 1 位置的值
// 所以现在的cn = cn + 1;
next[index ++] = ++cn;
}else if(next[cn] == -1){
// 已经不能在跳了那就是没有
next[index ++ ] = 0;
// 到了这个不那么坑定已经来到了数组中的0位置，那么此时cn =0;
// 此时index = 2 所以下面这句可以不要
cn = next[index - 1];
}else{
// 还能继续跳
cn = next[cn];
}
}
return next;
}
public static boolean isEqual(String a, String b) {
if (a == null && b == null) {
return true;
} else {
if (a == null || b == null) {
return false;
} else {
return a.equals(b);
}
}
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.left = new Node(2);
head1.right = new Node(3);
head1.right.left = new Node(4);
Node head2 = new Node(3);
head2.left = new Node(4);
System.out.println(subTree(head1, head2));
System.out.println( null == null);
}
}
