尝试用有限状态机解决一道算法题

• 有限状态机（Finite-State Machine）

　　　　有限状态机是一种数学模型，我理解的有限状态机的状态是表示做一件事情的不同阶段，条件和行为就是在不同阶段采取什么样的措施能达到下一阶段。

　　　　有限状态机分为有四个概念：初态，现态，次态，终态，条件，行为；

　　　　初态就是启动状态，现态就是当前状态，次态就是将要跳转到的下一个状态，每个FSM肯定有一个终态不然不能成为有限，条件就是状态跳转的条件，行为就是跳转到下一状态实施的动作。

　　　　例如电梯，从1楼到9楼它是在运行上升这个状态，而促使它停止的条件就是在1-9之间按下上行按键，它就会从运行状态变为停止在某楼层的状态。如果按下下行按钮就会等到它上升到最高楼层改变为下行的时候才会停留在某层。

• Beautiful String

　　　　描述：

　　　　　　　We say a string is beautiful if it has the equal amount of 3 or more continuous letters (in increasing order.)

　　　　　　　Here are some example of valid beautiful strings: "abc", "cde", "aabbcc", "aaabbbccc".

　　　　　　　Here are some example of invalid beautiful strings: "abd", "cba", "aabbc", "zab".

　　　　　　　Given a string of alphabets containing only lowercase alphabets (a-z), output "YES" if the string contains a beautiful sub-string, otherwise output "NO".

　　　　这个题目的意思是，形如abc，aabbcc这种连续的升序的并且长度为3个以上的是beautiful string，给定一个字符串，查找它是否包含beautiful string。

　　　　而我只注重如何计算，输入形式没有编写。

　　　　有限状态机这个思路是看网上博客的，但是他们并没有分析如何设计有限状态机。在分析的过程中，我们按着模型的特性来分析，比如读到一个字符串时候，状态机该做何反应，状态该如何切换。

　　　　我设计的有限状态机是按照它处理的字符为BS的第几个为界的，读到字符我们感兴趣的只有两个事件：当前字符与上一字符是相同的、当前字符是上一字符的+1，其余都是不感兴趣的事件。而在这两个事件里面，又存在index划分问题，比如它是BS的第一位，读到相同怎么处理，读到+1怎么处理。

　　　　代码如下：　　

package stateMachine;
/**
 * 规则：升序的小写字母，并且数目一致且字符数目大于3的的连续子串为Beauty String
 *         比如 abc，aabbcc，abcd等
 * 检查字符串中是否包含有BS
 * @author MacBook
 * 状态机：现态，次态，条件，动作
 * 1.当前字符；2.当前字符的数目；3.前一字符的数目；4.当前字符为第几个字符；
 * 
 * 检查字符串时候会发生：当前字符与上一字符相等、当前字符为上一字符+1、其他；
 * 
 * 当前字符与上一字符相等：1.第一位字符串，则count++;2.第二位字符串，则检查pre_num,若大于地index=1；3.第三位字符，若count不等于pre_num则countinue，等则break并设置result为true；
 * 当前字符为上一字符+1：1.index=1，则直接设置index=2并拷贝1所得信息；2.index=2，则拷贝信息后设置index=3；3.index=3，则检查是否count==pre_num,相等则result=true，否则设置为第index=2，拷贝信息；
 * 
 */
public class BeautyString {
    public static void main(String[] args) {
        new BeautyString().counting("aaab");
    }
    public void counting(String s){
        state Machine = new state();
        boolean result = false;
        Machine.setCurrent(s.charAt(0));
        Machine.setIndex(1);
        Machine.setCount(1);
        for(int i=1;i<s.length();i++){
            //当前字符与上一字符相同的时候
            if(Machine.getCurrent() == s.charAt(i)){
                Machine.setCount(Machine.getCount()+1);
                if(Machine.getIndex() == 1)
                    continue;
                else if(Machine.getIndex() == 2){
                    if(Machine.getPre_num() < Machine.getCount())
                    {
                        Machine.setPre_num(0);
                        Machine.setIndex(1);
                    }
                }else if(Machine.getIndex() == 3){
                    if(Machine.getCount() == Machine.getPre_num())
                    {
                        result = true;
                        System.out.println("条件1");
                        break;
                    }
                }
            //当前字符为上一字符+1的时候
            }else if(Machine.getCurrent() == s.charAt(i) - 1){
                if(Machine.index == 1){
                    Machine.setCurrent(s.charAt(i));
                    Machine.setPre_num(Machine.getCount());
                    Machine.setCount(1);
                    Machine.setIndex(2);
                }else if(Machine.index == 2){
                    Machine.setCurrent(s.charAt(i));
                    Machine.setPre_num(Machine.getCount());
                    Machine.setCount(1);
                    Machine.setIndex(3);
                    if(Machine.getCount() == Machine.getPre_num())
                    {
                        result = true;
                        System.out.println("条件2");
                        break;
                    }
                }else if(Machine.index == 3){
                    if(Machine.getCount() == Machine.getPre_num())
                    {
                        result = true;
                        System.out.println("条件3");
                        break;
                    }else{
                        Machine.setCurrent(s.charAt(i));
                        Machine.setPre_num(Machine.getCount());
                        Machine.setCount(1);
                        Machine.setIndex(2);
                    }
                }
            //其他
            }else{
                Machine.setCurrent(s.charAt(i));
                Machine.setIndex(1);
                Machine.setCount(1);
            }
            System.out.println(Machine.getCurrent()+" "+Machine.getCount()+" "+Machine.getPre_num()+" "+Machine.getIndex());
        }
        System.out.println(result);
    }
}
//状态机
class state{
    char current;
    int pre_num;
    int count;
    int index;
    public char getCurrent() {
        return current;
    }
    public void setCurrent(char current) {
        this.current = current;
    }
    public int getPre_num() {
        return pre_num;
    }
    public void setPre_num(int pre_num) {
        this.pre_num = pre_num;
    }
    public int getCount() {
        return count;
    }
    public void setCount(int count) {
        this.count = count;
    }
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    
}