package DataStructure;
import java.util.ArrayList;
import java.util.List;
//KMP算法的实现
//以下代码由freedom结合资料理解写出
public class DMPtest1 {
private int next[] ;
private String target; //主串
private String pattern;//子串
char[] t; //主串字符
char[] p; //子串字符
private static List<Integer> list ;
public DMPtest1() {}
public DMPtest1(String pattern,String target) {
this.pattern = pattern;
this.target = target;
p = this.pattern.toCharArray();
t = this.target.toCharArray();
//list = new ArrayList<Integer>(); //初始化一个集合用于保存匹配的子串在主串中的索引
next = this.getNextArray(this.pattern); //接受返回的已经算好的数组
}
public void displayNext() {
//打印next数组
for(int i=0;i<next.length; i++) {
System.out.print(next[i]);
}
}
public List<Integer> getTargetIndex() {
List<Integer> list = new ArrayList<Integer>();
int num=0;
int i = 0;//主串target下标
int j = 0;//子串pattern下标
if(t.length>=p.length) {
while(i<t.length) { //因为主串的下标是不变的，只有匹配超过他自己长度就会跳出循环
if(p[j]==t[i]) {
num++; //第一次相等的话那么num清零
j++;
i++;
//System.out.println("已经找到一个目标"+j+p.length);
if(j>p.length-1) {//若已经是最后一个数了
list.add(i-j); //把匹配的字符串在主串中位置（第一个字符的索引）添加到list
j=0;
//说明一个子串已经匹配完毕
//j已经等于p数组的最后一个下标的下一个下标了
}
}else {
//两字符不匹配的话
//j的新索引直接等于next[j]结论在纸上写着
if(num==0) {
j=0;
//第一次不相等，那么 i 需要自加
i++;
//这种结构要小心，一定要写在下一个if的前面！
}
if(num>0) {
//说明不是第一次不相等，那么主串下标不用自加
j=next[j];
num=0;
}
//System.out.println(j);
}
}
}else {
System.out.println("模式串必须 大于或等于 主串 ！");
}
return list;
}
/**
* 1 、该方法 用于返回一个next[]数组，保存的是模式串的相应T{0~j-1}字串的（最长前缀和后缀相同匹配字符的数量）j是模式串的下标
*
* 2 、 pattern是模式字符串，要转化成char[],如你要搜索freedom,就要把freedom，转成f,r,e,e,d,o,m的char类型数组
*
* 3、此方法是用递归的思想实现，可以一眼写出next数组。在后面会给解释！
*
*/
public int[] getNextArray(String pattern) {
int next[] = new int[p.length];
next[0] = -1;
int j = 0; //next数组下标
int k = -1; // 用于临时保存next数组的值
//因为next数组求出来后目的是为了求DMP，所以把整个next数组向右平移1，所以第一位普遍是-1,代表没有该字串
//而next[1]=0，因为第二个位置的字串求得是T{0~j-1}的前缀和后缀最长相同值的长度，所以1个字符是空集，这个会在方法体里面实现
//当j给最后一个字符赋完值,就要跳出循环，如果该字符串有8个字符，那么j必须小于8-1
while(j<p.length-1) {
if(k==-1||p[k]==p[j]) {
//如果匹配成功,j,k两下标都要自加，以比较下一个组合是否相等
j++;
k++;
next[j] = k;
} else {
//如果不匹配，那么j依然不动，k取上一个k的值
k = next[k]; //知道k为-1没有匹配值返回0
}
}
return next;
}
public static void main(String args[]) {
DMPtest1 dmp = new DMPtest1("abc","afwefwaefaaaaabcawiefjawoijfeioawjofabc"); //为next数组初始化了
//dmp.displayNext();
list = dmp.getTargetIndex(); //遍历匹配主串，并将索引返回给list
for(int i=0;i<list.size();i++) {
System.out.println("字符串在主串中的位置是"+list.get(i));
}
System.out.println("共有 {"+list.size()+"} 个匹配结果");
}
}