其实不得不承认，以前写的程序上传到Github都不够用心。甚至于花了很大力气的一些较大程序也没有一个简易的构建说明，甚至于说是更新要点。

自我反省了一下，争取把以前贴到Lofter上的技术博客慢慢的转移到Github以及这里的io上来。

本文的理解建立在此^1以及^2详解之上

本文是对 数据结构–C语言版 书中代码的详解与个人理解

在看到 数据结构–C语言版 里的字符串模式匹配算法时，一开始我不知情Knuth, Morris, Pratt模式匹配是何物，直到有一行代码

    i = failure[i];

真的是百思不得其解，应该说我对于i的作用并不是很明确。此书称此函数为失配函数，对于此数组的作用也算是略知了一二。我这里不赘述算法的基础介绍，着重于理解上可能产生歧义的几个部分。

首先我想先将书上KMP算法的实际匹配算法代码罗列一下。此书是将一段未知字符串先进行失配函数处理，得到failure数组，或者说是网络上说的next数组。

int pmatch(char *string, char *pat)
{
    // 字符串指针 / 模式字符串指针
    int i = 0, j = 0;
    // 命名上稍做了改动 方便理解
    int lengthString = strlens(string), lengthPat = strlens(pat);

    while(i < lengthString && j <lengthPat)
    {
        if(string[i] == pat[j])
        {
            i++;
            j++;
        }
        else if(j == 0)
            i++;
        else
            // 回到可回溯位置(核心)
            j = failure[j - 1] + 1;
    }        

    // 若完成匹配需要让i回归到模式匹配的起始位置
    return (j == lengthPat) ? (i - lengthPat), -1;
}

这里的核心代码确切的说只有一行，就是j = failure[j - 1] + 1。这里j起到的作用就是原文里这一段。

让匹配失败后，不是暴力求解的从pattern的第一位A开始，而是从failure[j-1]+1(在这里failure[j-1]指向的是第一位A，在+1了之后就指向了B)，这一点很重要，很多教程似乎都撇开了next / failure数组和实际求解的关系。

大多将这两者分开介绍，我在仔细联系了两者后发现，其实j = failure[j - 1] + 1这一段的理解是分不开失配函数的求解的。

以下是失配函数

void fail(char *pat)
{
    int n = strlen(pat);
    failure[0] = -1;

    for(int j = 0; j<n; j++)
    {
        // i在此处会被重置，要么为-1要么为上一循环结束值
        i = failure[j - 1];

        while(pat[j] != pat[i+1] && i>0)
            // 核心代码
            i = failure[i];

        if(pat[j] == pat[i+1])
            failure[j] = i+1;
        else
            failure[j] = -1;
    }
}

我想详说一下i的作用，很微妙，似乎不能用一句简单的话概括。还记得刚才匹配失败以后从failure[j-1]+1重新匹配的事实吗。i在这里就是表示，上一个p0,p1…pi = pj-i,pj-i+1…pj出现的位置，也就是前缀在后缀中出现的位置。后边的if/else应该是好理解的。

可以这样代入，某一循环中的某一刻，只要上一循环i>0, 那么pat[i]==pat[j-1]，因此failure[j-1] = i - 1无误(本书中i因为是从-1开始的，算法导论从0开始，本意相同，只有1的差距)。

所以倘若pat[i+1] == pat[j]那么自然failure[j]的值可以直接从上次结果failure[j-1]继承过来failure[j] = i+1了（i会在循环开始被重置为failure[j - 1]，因为我的条件是当前字符相同，所以不进入while），等价于failure[j] = failure[j-1] + 1咯。

核心代码

    i = failure[i];

的理解我花了非常多的时间。

感觉直到目前为止，都没能很透彻的了解。

一天一个hello world 我都嫌烦了 daddy大法好啊!

请注意 以下是展示我C++程序员前端实力的时候了……以下所有内容都是我在练习Markdown语法

我就一句话，千万不要再喊我做万花筒了……

啥都不说了，上架完万花筒我就算是升华了。

什么？毕设要做万花筒？不行了，我肚子疼。

有事别找我，没事烧纸谢谢。

听说你赚钱了？哦，被打断腿赔了20万。

你是喊我去创业吗，公司在哪？在心里，哦，滚。

P78 中讲到

while((char c = cin.get()) != 'q')

这里c的结果会得到一张笑脸

作者说while if switch里不能插入括号

事实上 原文作者的意思是这样的 并非不能插入括号 而是说char c这样的语句放在括号中是不行的

// error
while((char c = cin.get()) != 'q')
{

}

// correct
while(char c = cin.get() != 'q')
{

}

因为char c = ...这里c的作用域只在括号中 所以超出了范围自动回收 并不能参与运算 正确的写法应该是

while(char c = cin.get() != 'q')

这里的!=优先级比 = 要高

所以c得到的不是cin返回的字符串 而是一个bool 所以大多数情况下回显示一个笑脸

1.

// 传递表给Lua
lua_createtable(luaState, 2, 0);
// [1]->49
// 1代表key值 一个键值指定一个value 类似于号码簿
lua_pushnumber(luaState, 1);
lua_pushnumber(luaState, 49);

// 压入两个参数之后索引变为-3 栈顶为-1
lua_rawset(luaState, -3);

// [2]->"Life is a Circle"
lua_pushnumber(luaState, 2);
lua_pushstring(luaState, "Life is a Circle");
// 上一步rawset已经清空栈 再次压入两个元素变为-3
lua_rawset(luaState, -3);

lua_setglobal(luaState, "tables");

搭配Lua文件中的

-- #table为获取当前table长度
for i=1, #tables do
     print(i, tables[i])
end

2.数组在Lua中只不过是整数的Table而已 比如一个table作为array的时候可以是这样的
array = {12, “hello world”} (与C/C++类型确定语言不同的是 Lua数组里的元素可以是任何Lua类型 而C/C++规定了只能是一种类型)

print(array[1])
print(array[3])

Lua的数组下标是从1开始的 因此倘若你越界访问会得到一个nil值

print(array[0]) --nil 
print(array["1"]) --nil

(和array[1]的区别：一个是integer作为key,一个是字符串做为key)

1.在Lua中完成全局函数的绑定时 要注意 调用这个函数需要放在pcall之后 因为在这之前 栈一直是空的
而pcall的作用就是讲lua文件编译 并将全局变量(函数是闭包也就是一个变量)压栈 这时候对整个儿自定义的方法进行的操作才是有意义的
不然会得到unprotected error in call to Lua API (attempt to call a nil value)的错误

2.但凡是对全局变量进行的预先处理操作 可以在lua_pcall之前完成 而那些需要使用到全局变量(如返回值 闭包等变量)的一定要等到pcall完成 也就是编译压栈全局变量完成之后才能进行 不然也会报unprotected error in call to Lua API (attempt to call a nil value)的错误

比如 尝试返回三个值
– local表示存在于栈中的变量 而不是存在与table中的全局变量

local temp = {9, "hehehe"}
return temp,9,1

在C程序中

std::stringstream strBuffer;
while(lua_gettop(luaState))
{
    strBuffer.str(std::string());
    strBuffer << "lua returned a ";

    int index = lua_gettop(luaState);
    switch(lua_type(luaState, index))
    {
    case LUA_TNUMBER:
        strBuffer << "number" << lua_tonumber(luaState, index);
        break;
    case LUA_TTABLE:
        strBuffer << "table";
        break;
    case LUA_TSTRING:
        strBuffer << "string" << lua_tostring(luaState, index);
        break;
    case LUA_TBOOLEAN:
        strBuffer << "boolean" << lua_toboolean(luaState, index);
        break;
    default:
        strBuffer << "unknow type";
        break;
    }

    strBuffer << "\n";
    lua_pop(luaState, 1);
    cout << strBuffer.str() << endl;
}

期望能够解析出每个返回值的类型信息

这一步的操作就应该放在pcall之后 不然会发现操作的栈都是空的 那么就都是对nil进行的非法操作