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

发布时间:2024年01月12日

简介

状态机(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…)

文章来源:https://blog.csdn.net/zzz19920821/article/details/135533773
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。