状态机和相关算法应用分析

简介

状态机（State Machine）在软件编程中是一个数学模型，可以用状态转移图表示，指的是：现态在满足某个条件时，进行动作（状态转移），从而转为另一个状态（次态）

状态机的4个要素：现态、条件、动作、次态。“现态”和“条件”是因 ，“动作”和“次态”是果。

1）现态：指当前所处状态；

2）条件：又称“事件”。当条件被满足时，将会触发一个动作，或者执行一次状态的迁移。

3）动作：条件满足后执行的动作。条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必须的，当条件满足后，也可以不执行任何动作，迁移到新状态。

4）次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就变成新的“现态”了。

KMP算法

在长度为N的字符串txt中，搜索长度为M的子串pat
KMP是字符串匹配算法，时间复杂度O(M+N),空间复杂度O(M)

暴力搜索，时间复杂度，O(MN)，空间复杂度O(1)

状态分析

现态：当前匹配情况
条件：当前字符
动作：根据条件确定怎么转移
两种可能，
1：当前匹配字符成功，状态+1；
2：当前匹配字符失败，状态回退（核心点，通过回退到最长子前缀，避免从头匹配，提高效率）
次态：转移后的新状态，判断是否到达需要的状态，到达则算法终止

dp[j][c] = next【状态转移方程dp[现态][字符] =新状态】
0 <= j < M，代表当前的状态
0 <= c < 256，代表遇到的字符（ASCII 码）
0 <= next <= M，代表新状态

代码实现

package practice.dp;
/**
 * https://mp.weixin.qq.com/s/r9pbkMyFyMAvmkf4QnL-1g
 *
 * KMP 算法最关键的步骤就是构造这个状态转移图。要确定状态转移的行为，
 * 得明确两个变量，一个是当前的匹配状态，另一个是遇到的字符；
 * 确定了这两个变量后，就可以知道这个情况下应该转移到哪个状态。
 */
public class KMP {

    /**
     * dp[j][c] = next
     * 0 <= j < M，代表当前的状态
     * 0 <= c < 256，代表遇到的字符（ASCII 码）
     * 0 <= next <= M，代表下一个状态
     *
     * dp[4]['A'] = 3 表示：
     * 当前是状态 4，如果遇到字符 A，
     * pat 应该转移到状态 3
     *
     * dp[1]['B'] = 2 表示：
     * 当前是状态 1，如果遇到字符 B，
     * pat 应该转移到状态 2
     */
    private int[][] dp;
    /**
     * 搜索字符串
     */
    private String pat;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();

        //最长回退子串的状态，如果有公共前缀，不为0，如果没有则为0
        int X = 0;

        //dp[状态][字符] = 下个状态
        dp = new int[M][256];
        dp[0][pat.charAt(0)] = 1;
        //构建状态转移图【现态 在 遇到 字符 后，进行状态转移】
        for(int j = 1; j < M; j++) {
            //状态j遇到字符[^pat.charAt(j)]后，状态迁移【回退】
            for (int c = 0; c < 256; c++) {
                dp[j][c] = dp[X][c];
            }
            //状态j遇到字符[pat.charAt(j)]后，状态迁移【+1】
            dp[j][pat.charAt(j)] = j+1;

            //最长回退子串的状态X遇到pat.charAt(j)，进行状态迁移【可能+1，可能继续回退】
            X = dp[X][pat.charAt(j)];
        }

    }

    public int search(String txt) {
        int M = pat.length();
        int N = txt.length();
        //当前匹配状态
        int j = 0;
        for (int i = 0; i < N; i++) {
            j = dp[j][txt.charAt(i)];
            //状态迁移到M，表示匹配成功
            if(j == M) return i - M + 1;
        }
        // 没到达终止态，匹配失败
        return -1;
    }

    public static void main(String[] args) {
        String pat = "ababc";
        String txt = "abababsababc";
        KMP kmp = new KMP(pat);
        //7
        System.out.println(kmp.search(txt));
    }

}

股票买卖

一个方法团灭 LeetCode 股票买卖问题
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for …
dp[状态1][状态2][…] = 择优(选择1，选择2…)