【LeetCode 28】KMP算法

本文主要是介绍【LeetCode 28】KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

public class KMP {

	int[] next;
	String pattern;
	String target; 
	
	KMP(String target, String pattern) {
		this.pattern = pattern;
		this.target = target;
		this.next = new int[this.pattern.length()];
	}
	
	public void createNext() {
		int j = 0;
		int i = 1;
		this.next[0] = 0;
		if (pattern.length() >= 2) // 至少有两个字符才能比较前缀和后缀
		{
			while (i < pattern.length()) 
			{
				// i 表示要计入的next数组的位置
				while (i < pattern.length() && pattern.charAt(i) == pattern.charAt(j))
				{
					next[i] = j+1;
					i++;
					j++;
				}
				while (j > 0 && i < pattern.length() && pattern.charAt(i) != pattern.charAt(j))
				{
					j = next[j-1];
				}
				// 一直查找到j = 0
				if (i < pattern.length() && pattern.charAt(i) != pattern.charAt(j)) 
				{
					next[i] = 0;
					i++;
				}
				// 此时j > 0
				else if (i < pattern.length() && pattern.charAt(i) == pattern.charAt(j))
				{
					next[i] = j+1;
					i++;
					j++;
				}
			}
		}
	}
	
	public void showNext() {
		for (int i = 0; i < this.next.length; i++)
			System.out.print(this.next[i]);
	}
	
	public int findStr() {
		int i = 0; // 标识主串的位置
		int j = 0; // 表示模式串的位置
		int ret = -1;
		while (true)
		{
			int rem = i - j; // j表示已经匹配的字符个数
			while (i < this.target.length() && j < this.pattern.length())
			{
				if (this.target.charAt(i) != this.pattern.charAt(j))
					break;
				i++;
				j++;
			}
			if (this.target.length() - rem < this.pattern.length()) // target剩余的字符串长度短于pattern
				break;
			if (j == this.pattern.length()) // 已经找到pattern的起始位置
			{
				ret = rem;
				break;
			}
			else if (j > 0) // 第二个字符开始出现不匹配，此时回退，回退后的新字符还是在主串的原位置进行比较
				j = this.next[j-1];
			else if (j == 0) // 第一个字符就不匹配
				i++;
		}
		return ret;
	}
	
	public static void main(String[] args) {
		KMP k = new KMP("abcaabaaab", "aabaaab");
		k.createNext();
		k.showNext();
		System.out.println();
		System.out.println(k.findStr());
	}
}

其中，next数组的构造过程参见答案提供的思路

这篇关于【LeetCode 28】KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！