题目来源
https://leetcode.com/problems/regular-expression-matching/

内容：实现一个能支持”.” “*”的模式匹配程序，并判断是否整个都匹配上。例如：

isMatch("aa","a") -> false
isMatch("aab","c*a*b") -> true

做法比较传统，用自动机来做。

自动机形如下方（其表达式为c*aa*bb*）：

当状态为s1的时候，如果此处读到的数据是a的话，可以进入状态s2。

那么对于 表达式为”a*ab”怎么办？
它既要适配”ab”,“aab”,“aaab”…
其实可以用一个栈stackSavePoint保存这种(a*)既可以读当前的数据,也可以直接跳过到下一个这种类型的节点，保存当前数据的index，然后直接将当前数据交由下一状态处理。如果遇到当前状态并不能处理，则从stackSavePoint栈中弹出一节点，当前状态转到这一节点，并将当前数据的指针指向（index + 1），也就是回退N-1步，效率有点低，但还是前进了一步。

具体代码如下：

@H_301_45@class Solution {
@H_301_45@public:

// c*cab

    @H_301_45@struct Node {
        @H_301_45@bool isEverything;
        @H_301_45@bool isSelfContain;
        @H_301_45@char accept;
        @H_301_45@struct Node* son;
    };

    @H_301_45@struct Node* addNode(@H_301_45@struct Node* parent,@H_301_45@char ch) { // return current node after added.

        @H_301_45@struct Node* son = parent->son;

        @H_301_45@if (ch == '*') {
            parent->isSelfContain = @H_301_45@true;
            @H_301_45@return parent;
        }

        @H_301_45@struct Node* newSon = (Node*)malloc(@H_301_45@sizeof(@H_301_45@struct Node));
        newSon->accept = ch;
        newSon->isEverything = '.' == ch;
        newSon->isSelfContain = @H_301_45@false;
        newSon->son = NULL;
        parent->son = newSon;
        @H_301_45@return newSon;
    }

    // to merge something like a*a*a*a*b => a*b or .*a*b*c*d => .*d
    @H_301_45@struct Node* mergeSameNeighbour(@H_301_45@struct Node* parent) {
        @H_301_45@struct Node* header = parent;
        @H_301_45@while (parent && parent->son) {
            @H_301_45@if (parent->isSelfContain && parent->son->isSelfContain) {
                @H_301_45@bool isEverything = parent->isEverything || parent->son->isEverything;
                @H_301_45@if (isEverything || parent->accept == parent->son->accept) {
                    parent->isEverything = isEverything;
                    @H_301_45@struct Node* tmp = parent->son;
                    parent->son = parent->son->son;
                    free(tmp);
                }
            }
            parent = parent->son;
        }
        @H_301_45@return header;
    }

    @H_301_45@bool isMatch(string s,string p) {

        @H_301_45@if (p.empty()) {
            @H_301_45@return s.empty();
        }

        Node* emptyHeader = (Node*) malloc(@H_301_45@sizeof(@H_301_45@struct Node));
        Node* current = emptyHeader;
        @H_301_45@int index = 0;
        @H_301_45@int len = p.length();
        @H_301_45@while (index < len) {
            current = addNode(current,p.at(index++));
        }
        mergeSameNeighbour(emptyHeader->son);
        index = 0;
        len = s.length();
        stack<Node*> savePoint;
        stack<@H_301_45@int> saveIndex;
        current = emptyHeader->son;
        @H_301_45@while (index < len) {
            @H_301_45@char ch = s[index];
            @H_301_45@if (!current) {
                @H_301_45@goto helpme;
            }
            // printf("char[%d]: %c,current: %c\n",index,ch,current->accept);
            @H_301_45@if (current->isSelfContain) {
                @H_301_45@if (current->isEverything) {
                    // call me out when you cannot handle it
                    savePoint.push(current);
                    saveIndex.push(index);
                } @H_301_45@else @H_301_45@if (current->accept == ch) {
                    savePoint.push(current);
                    saveIndex.push(index);
                } 
                current = current->son;
                @H_301_45@continue;
            }

            @H_301_45@if (current->isEverything || current->accept == ch) {
                index++;
                current = current->son;
                @H_301_45@continue;
            }
            helpme:
            @H_301_45@if (savePoint.size()) {
                current = savePoint.top();
                savePoint.pop();
                @H_301_45@int lastIndex = saveIndex.top();
                saveIndex.pop();
                index = lastIndex + 1;
            } @H_301_45@else {
                @H_301_45@return @H_301_45@false;
            }
        }
        free(emptyHeader);
        /* in here,the test word run out,so we just find whethere the rest is NULL,or all are selfContain,which can be regarded as 0 */
        @H_301_45@while(current) {
            @H_301_45@if (current->isSelfContain) {
                current = current->son;
            } @H_301_45@else {
                @H_301_45@return @H_301_45@false;
            }
        }
        @H_301_45@return !current;
    }
};

这里有个问题， 如果需要支持[a-zA-Z.*-+]等的话，估计在Node.accept 中修改成keymap的形式，估计问题应该不是很大。