KMPアルゴリズムの簡単な実現

ウェブアプリケーションの開発や枠組み学習、応用、アーキテクチャの悟りなど、アルゴリズムの存在がほとんど見られない場面に力を入れています.しかし、これはこれからはアルゴリズムに接触しないという意味ではなく、JDKパッケージの良いAPIライブラリをひたすら把握しています.今日はStringのindexOfを使っていますが、突然この方法の実現を見たくなりました.
      1.6.0.17のアルゴリズムは主要コードを実現する:
     

for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j] ==
                         target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;

このアルゴリズムは単純マッチングを使用しています.最初にマッチする文字を見つけて、現在の後に新しいポインタを作成して、第二の文字を指して、残りの文字をマッチングします.このアルゴリズムは、実際にはiポインタが一致していないときに収縮ポインタに相当する.時間の複雑さは二列の長さの積です.長い文字列のマッチングがないと思いますので、最適化しないといけないですか?それともアルゴリズムを間違えて理解しました.
      このアルゴリズムはあまり良くないと思います.長い文字列の整合効率はあまりよくないので、データ構造の中で絶賛されたKMPパターンマッチングアルゴリズムを見なければなりません.具体的なアルゴリズムの原理は斧をいじらないで、優秀な牛達はとっくにネット上で多すぎる優秀な解説を残しました.私は原理を理解した後、Javaのコードを共有します.

public class KmpTest {

	/**The Next() function of The KMP algorithm.
	 * @param chars
	 * @return
	 */
	private int[] createNext(char[] chars) {
		int len = chars.length;
		int[] nextArr = new int[len];
		int i = 0, j = -1;
		while (i < len - 1) {
			if ((j == -1) || (chars[j] == chars[i])) {
				i++;
				j++;
				if (chars[j] != chars[i]) {
					nextArr[i] = j + 1;
				} else {
					nextArr[i] = nextArr[j];
				}
			} else {
				j = nextArr[j] - 1;
			}
		}
		return nextArr;
	}

	/**The default method which can find the index of a pattern String in a specific String.
	 * Pattern from the first character of the specific String.
	 * @param str
	 * @param pattern
	 * @return
	 */
	public int kmpIndex(String str, String pattern) {
		return kmpIndex(str, pattern, 0);
	}

	/**Pattern from a specific postion of the specific String.
	 * @param str
	 * @param pattern
	 * @param pos
	 * @return
	 */
	public int kmpIndex(String str, String pattern, int pos) {
		char[] strChars = str.toCharArray();
		char[] ptenChars = pattern.toCharArray();
		int len = strChars.length;
		int[] next = createNext(ptenChars);
		int i = pos - 1, j = -1;
		while (i < len && j < next.length) {
			if ((j == -1) || (strChars[i] == ptenChars[j])) {
				i++;
				j++;
			} else {
				j = next[j] - 1;
			}
		}
		if (j > next.length - 1) {
			return i - next.length;
		} else {
			return -1;
		}
	}

}

あとは簡単なtest caseです.

import junit.framework.Assert;
import junit.framework.TestCase;

public class KmpTestCase extends TestCase {

	KmpTest kmpTest;

	@Override
	protected void setUp() throws Exception {
		kmpTest = new KmpTest();
	}

	public void testKmpIndex() {
		Assert.assertEquals(0, kmpTest.kmpIndex("ababaababc", "ababa"));
		Assert.assertEquals(2, kmpTest.kmpIndex("ababaababc", "abaab"));
		Assert.assertEquals(6, kmpTest.kmpIndex("ababaababc", "babc"));
		Assert.assertEquals(-1, kmpTest.kmpIndex("ababaababc", "baabc"));

		Assert.assertEquals(2, kmpTest.kmpIndex("ababaababc", "abaa", 2));
		Assert.assertEquals(-1, kmpTest.kmpIndex("ababaababc", "abaa", 3));
	}

}

アルゴリズムのこの技量はプログラマがプログラムの生命の源を維持します.あるいは内功です.私にとって、基本的な練習には大きなエネルギーが必要です.私はやはり日常の仕事の中で練習します.