数组（Array）

滑动窗口

LeetCode 209 长度最小的子数组

KMP 算法

• LeedCode: 28. 找出字符串中第一个匹配项的下标 （KMP 特解）
• LeetCode：459.重复的子字符串 （KMP 特解） todo

解决字符串匹配问题： indexOf

理论

参考：

1. 手工 https://www.bilibili.com/video/BV1UN4y1u7Nx/
2. 代码 https://www.bilibili.com/video/BV1HT411V71d/

关键：前缀表（next） —— 找到已匹配的前缀长度

前缀例子：

字符串： aabaa
前缀：
a
aa <--
aab
aaba
后缀：
a
aa <--
baa
abaa

字符串： aabaaf
前缀： x--
a
aa
aab
aaba
aabaa
后缀： x--
f
af
aaf
baaf
abaaf

关键：生成前缀表 —— 求最长相等前缀、后缀

字符串： aabaaf
最长相等前后缀： 片段 -> 子段 -> 前缀 -> 后缀 -> 长度
a -> null -> -1 -> -1 ->  -1 （无字段）
aa -> a -> null -> null -> 0 （无前缀/后缀）
aab -> aa -> a -> a -> 1
aaba -> aab -> aab -> aab -> 0 （不包含全段）
aabaa -> aaba -> a -> a -> 1
aabaaf -> aabaa -> aa -> aa -> 2
前缀表：
-1 0 1 0 1 2

例子2
ababac
-1 0 0 1 2 3

代码

package org.example.string;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;

@Slf4j
class KMSTest {
    @Test
    void test() {
        assertEquals(0, "xxx".indexOf(""));
    }

    @Test
    void test00() {
        char[] arr = "".toCharArray();
        int[] expectNext = new int[]{};
        int[] expectNextVal = new int[]{};
        assertNextFunc(arr, expectNext, expectNextVal);
        assertIndexOf(arr, "ababac");
    }

    @Test
    void test01() {
        char[] arr = "ababac".toCharArray();
        int[] expectNext = new int[]{-1, 0, 0, 1, 2, 3};
        int[] expectNextVal = new int[]{-1, 0, -1, 0, -1, 3};
        assertNextFunc(arr, expectNext, expectNextVal);
        assertIndexOf(arr, "ababac");
        assertIndexOf(arr, "aababac");
        assertIndexOf(arr, "abababac");
        assertIndexOf(arr, "abababacf");
        assertIndexOf(arr, "ababa-bacf");
    }

    @Test
    void test02() {
        char[] arr = "aabaaf".toCharArray();
        int[] expectNext = new int[]{-1, 0, 1, 0, 1, 2};
        int[] expectNextVal = new int[]{-1, -1, 1, -1, -1, 2};
        assertNextFunc(arr, expectNext, expectNextVal);
    }

    @Test
    void test03() {
        char[] arr = "abababab".toCharArray();
        int[] expectNext = new int[]{-1, 0, 0, 1, 2, 3, 4, 5};
        int[] expectNextVal = new int[]{-1, 0, -1, 0, -1, 0, -1, 0};
        assertNextFunc(arr, expectNext, expectNextVal);
    }

    private void assertNextFunc(char[] arr, int[] expectNext, int[] expectNextVal) {
        KMS kms = new KMS();
        int[] next = kms.genNext(arr);
        log.info("next: {}", next);
        assertArrayEquals(expectNext, next);
        kms.toNextVal(arr, next);
        log.info("next: {}", next);
        assertArrayEquals(expectNextVal, next);
    }

    private void assertIndexOf(char[] arr, String str) {
        Integer indexOf = str.indexOf(String.valueOf(arr));
        assertEquals(indexOf, new KMS().indexOf(arr, str.toCharArray()));
    }
}