在VC下面学习OpenGL

发表于 2012-11-06 分类于图形学， OpenGL 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

先贴一个OpenGL程序的代码,

#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glut.h>
#pragma comment(linker, "/subsystem:\"windows\" /entry:\"mainCRTStartup\"") //设置连接器选项

const int WINDOW_WIDTH = 640;
const int WINDOW_HEIGHT = 480;
const int WINDOW_POS_X = 300;
const int WINDOW_POS_Y = 150;
const int NUM = 1000;

void myInit()
{
    glClearColor(1.0, 1.0, 1.0, 0.0);//设置背景颜色为亮白
    glColor3f(0.0f, 0.0f, 0.0f);//设置绘图颜色为黑色
    glPointSize(4.0);//设置点的大小为4*4像素
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(0.0, WINDOW_WIDTH, 0.0, WINDOW_HEIGHT);//以上三句话合起伙是设置窗口的坐标系
}

void myDisplay()
{
    glClear(GL_COLOR_BUFFER_BIT);//清屏
    glBegin(GL_POINTS);
    for (int i = 0; i < NUM; ++i)
    {
        glVertex2i(rand() % WINDOW_WIDTH, rand() % WINDOW_HEIGHT);
    }
    glEnd();
    glFlush();//送往设备显示
}

int main(int argc, char** argv)
{
    glutInit(argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);//设置显示模式
    glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);
    glutInitWindowPosition(WINDOW_POS_X, WINDOW_POS_Y);
    glutCreateWindow("散乱点图");
    glutDisplayFunc(myDisplay);//注册重绘回调函数
    myInit();
    srand(time(NULL));
    glutMainLoop();//进入消息循环

    return 0;
}

该程序只是创建一个窗口，然后在里面画一些随机的点。效果如图所示，

说实话这个程序非常简单，在主函数里面只是设置了窗口大小和位置，然后创建了个窗口，做了些初始化，并且为窗口设置了显示回调函数。初始化函数里面都有注释，显示回调函数里面只是一直在随机画点而已。

说实话，仅仅是使用最基本的opengl画图确实太简单了，也没什么多说的，如果你熟悉Windows程序设计和C++语言，只是换个库而已，真正需要学习的是计算机图形学。我觉得OpenGL相对于DirectX简洁明了很多了，所以才选择了计算机图形学OpenGL版这本书来学习图形学的。下面来简要介绍下OpenGL的库组成吧。

OpenGL库分为四个部分，GL和GLU，GLUT以及GLUI。GL和GLU都是用于绘图的，只是第一个是基本库，第二个是一些高级的绘图函数。GLUT库主要包含一些管理窗口和菜单的函数，GLUI则是一些高级的界面管理部分，比如各种复杂的按钮和菜单。

我觉得如果在VC下面建立控制台工程，然后设置链接命令去掉控制台窗口，再在main函数下执行OpenGL操作，这个过程不仅简洁而且感觉效果也不错。现在看来，OpenGL确实是一个比较美观的东西，至少相对于我用了几年的MFC来说。

Console工程下如何不显示控制台黑窗口只显示Windows窗口

发表于 2012-11-06 分类于 MFC 阅读次数： Valine：
本文字数： 957 阅读时长 ≈ 1 分钟

本文是以OpenGL的代码为例子的。计算机图形学OpenGL版上面的例子都是控制台模式的，如果不进行设置，运行的时候会先出现黑窗口再出现Windows窗口。

其实要去除控制台窗口非常简单，只需要修改工程设置，把子系统改成Windows，程序的入口点改成mainCRTStartup。

下面我先把几中解决办法列举出来，再解释下我的理解。

方法一：在程序中加入一句#pragma comment(linker, “/subsystem:\”windows\” /entry:\”mainCRTStartup\””)，建议加在include的后面。

方法二：修改工程设置。

对于vc6，地方在Project->setting->Link->Project Options。

点开后的界面如图，

在右下角的Project Options里面找到/subsytem:,并把其后面其后面的参数改成为windows,然后再找到/entry:，把其后面的值改成”mainCRTStartup”，如果找不到就添加，最后的效果是/subsystem:windows /entry:”mainCRTStartup”。

对于vs2008，地方在项目->属性->链接器，

然后在左边选中高级，如图所示，

在最上面的入口点输入mainCRTStartup，再选中系统，如图所示，

在最上面的子系统选择Windows即可了。

为什么这样设置下就可以了了。主要是因为Windows系统下有几种子系统，一种是控制台，一种是窗口子系统，如果建立了控制台工程肯定是要创建控制台子系统程序了，建立了Windows Application和MFC之类的工程则是窗口子系统了。不同的子系统会链接不同的主函数，控制台的会链接main,窗口的会链接WinMain，如果不匹配肯定会链接失败。

现在我们使用OpenGL编程，又建立的是控制台工程，如果不进行设置肯定会出现黑窗口的，所以我们把工程的子系统改成Windows，但是我们不想改主函数为WinMain了，因为这样会很麻烦，所以我们再把程序入口改成mainCRTStartup。同样如果是win32 App工程下，我们可以把子系统改成控制台，再设置程序入口为WinMainCRTStartup，应该就会得到相反的效果了。

Begin Graphics With OpenGL(在vc6和vs2008下使用OpenGL进行编程)

发表于 2012-11-04 分类于图形学， OpenGL 阅读次数： Valine：
本文字数： 1k 阅读时长 ≈ 1 分钟

首先，我们需要安装好VC6或者VS2008，然后获取OpenGL的开发包。剩下的一件麻烦事情就是配置了。

如果你找不到合适的开发包，可以从我这里下载，里面开发包和查询手册，可是我辛苦收集好的哦。地址：OpenGL SDK

在你下载好的开发包里面，会出现三个目录，分别是include和lib,system32。include里面当然是OpenGL的头文件了，那么lib则是动态链接时候的导入库了，system32里面是几个dll，dll你知道该放在哪里吧，放在你的程序同一个目录下，或者干脆放在系统目录下，即c盘下面的system32目录。开发包里面有个txt文件简要说明了如何设置include和lib，下面我要用图示详细说明vc6和vs2008下的设置方法。

vc6下的设置，
step1:
Tools->Options->directories

step2:
在Show Directories For选型卡里面选择include files
然后,在下面的directories里面添加一个新项，然后选择opengl的include目录，再用右上角的箭头上移到最上面。

step3:
在Show Directories For选型卡里面选择Library files
然后,在下面的directories里面添加一个新项，然后选择opengl的lib目录，再用右上角的箭头上移到最上面。

step4:
把opengl开发包里面的system32文件下面的dll全部拷贝的C:\WINDOWS\system32下面，当然不同的系统这个目录不同，
不过这都是系统目录。

现在你就可以用vc6下使用opengl学习图形学了。。。

vs2008下的设置,
step1:
工具->选项，打开如图所示的对话框，
点开左边的项目和解决方案，选择里面的vc++目录。

step2:
类似vc6下面的设置，在右边的显示一下内容的目录选项卡中选择包含文件，再在下面的列表框里面添加一个新的目录作为新的include目录。目录的路径设置同vc6，就是开发包的include文件夹。

step3:
类似vc6下面的设置，在右边的显示一下内容的目录选项卡中选择库文件，再在下面的列表框里面添加一个新的目录作为新的lib目录。目录的路径设置同vc6，就是开发包的lib文件夹。

step4:
同样是拷贝dll到系统目录下。

至此基本解决了，无论是哪种外部库的设置都是如果搞一下就ok了，无论是哪个版本的vs，基本上设置的地方差别不大。

poj 3264 Balanced Lineup St算法建立Rmq

发表于 2012-10-25 分类于算法，算法题阅读次数： Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

ST算法可以说就是个二维的动态规划，黑书上有解释。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

const int MAX_I = 50010;
const int MAX_J = 20;

int nMax[MAX_I][MAX_J];
int nMin[MAX_I][MAX_J];
int nArr[MAX_I];
int nN, nQ;

void InitRmq(int nN)
{
    for (int i = 1; i <= nN; ++i)
    {
        nMax[i][0] = nMin[i][0] = nArr[i];
    }

    for (int j = 1; (1 << j) <= nN; ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= nN; ++i)
        {
            nMax[i][j] = max(nMax[i][j - 1],
                             nMax[i + (1 << (j - 1))][j - 1]);
            nMin[i][j] = min(nMin[i][j - 1],
                             nMin[i + (1 << (j - 1))][j - 1]);                
        }
    }
}

int Query(int nA, int nB)
{
    int k = (int)(log(1.0 * nB - nA + 1) / log(2.0));
    int nBig = max(nMax[nA][k], nMax[nB - (1 << k) + 1][k]);
    int nSml = min(nMin[nA][k], nMin[nB - (1 << k) + 1][k]);
    return nBig - nSml;
}

int main()
{
    while (scanf("%d%d", &nN, &nQ) == 2)
    {
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%d", &nArr[i]);
        }
        InitRmq(nN);
        for (int i = 0; i < nQ; ++i)
        {
            int nA, nB;
            scanf("%d%d", &nA, &nB);
            printf("%d\n", Query(nA, nB));
        }
    }

    return 0;
}

hdu 3068 最长回文 Manacher算法

发表于 2012-10-24 分类于算法，算法题阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

该题就是求一个字符串的最长回文子串，就是一个满足本身是回文的最长的子串。
该题貌似可以用后缀数组和扩展kmp做，但是好像后缀数组貌似会tle，改学了下一个专门的叫Manacher算法的东西。。。
这又是一个线性改良算法。找到有篇文章写的不错，链接如下：
http://www.felix021.com/blog/read.php?2040。
该算法说起来也不是太复杂，比较容易看懂的那种，当然是接触过其它字符串算法的前提下了。记得以前就看了看，硬是没看懂，想不到现在这么快就明白了。
该算法需要额外的O(N)空间。说起来是空间换时间吧。
大概的思路是先预处理字符串，使其成为一个长度一定为偶数的串。而且第一个字符是’$’，假设’$’没有在原串出现过。然后再在原来的每个字符前面加上’#’，最后再加个
‘#’。比如，abc就变成了$#a#b#c#。现在再对新的字符串进行处理。
开一个新的数组nRad[MAX]，nRad[i]表示新串中第i个位置向左边和向右边同时扩展并且保持对称的最大距离。如果求出了nRad数组后，有一个结论，nRad[i]-1恰好表示原串对应的位置能够扩展的回文子串长度。这个的证明，应该比较简单，因为新串基本上是原串的2倍了，而且新串每一个有效字符两侧都有插入的#，这个找个例子看下就知道是这样了。
最重要的是如何求出nRad数组。
求这个数组的算法也主要是利用了一些间接的结论优化了nRad[i]的初始化值。比如我们求nRad[i]的时候，如果知道了i以前的nRad值，而且知道了前面有一个位置id，能够最大的向两边扩展距离max。那么有一个结论，nRad[i] 能够初始化为min(nRad[2*id - i], max - i)，然后再进行递增。关键是如何证明这个，这个的证明，对照图片就很清楚了。
证明如下：
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，
以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。

当 P[j] > mx - i 的时候，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于
对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会
扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。

这个就说明得很清楚了。。。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 110010 * 2;
char szIn[MAX];
char szOut[MAX];
int nRad[MAX];

int Proc(char* pszIn, char* pszOut)
{
    int nLen = 1;

    *pszOut++ = '$';
    while (*pszIn)
    {
        *pszOut++ = '#';
        nLen++;
        *pszOut++ = *pszIn++;
        nLen++;
    }
    *pszOut++ = '#';
    *pszOut = '\0';

    return nLen + 1;
}

void Manacher(int* pnRad, char* pszStr, int nN)
{
    int nId = 0, nMax = 0;

    //pnRad[0] = 1;
    for (int i = 0; i < nN; ++i) 
    { 
        if (nMax > i)
        {
            pnRad[i] = min(pnRad[2 * nId - i], nMax - i);
        }
        else pnRad[i] = 1;

        while (pszStr[i + pnRad[i]] == pszStr[i - pnRad[i]])
        {
            ++pnRad[i];
        }
        if (pnRad[i] + i > nMax)
        {
            nMax = pnRad[i] + i;
            nId = i;
        }
    }
}

int main()
{
    while (scanf("%s", szIn) == 1)
    {
        int nLen = Proc(szIn, szOut);
        Manacher(nRad, szOut, nLen);
        int nAns = 1;
        for (int i = 0; i < nLen; ++i)
        {
            nAns = max(nRad[i], nAns);
        }
        printf("%d\n", nAns - 1);
    }

    return 0;
}

poj 3294 Life Forms 后缀数组求至少出现在K个字符串中的最长公共子串

发表于 2012-10-24 分类于算法，算法题阅读次数： Valine：
本文字数： 3.8k 阅读时长 ≈ 3 分钟

此题就是给出N个字符串，然后求一个最长的子串，它至少出现在N/2+1个字符串中，如果有多个这样的子串，按字典序输出，如果没有这样的子串，输出?。
此题是罗穗骞论文里面的例11，他有讲述具体的解法。要用后缀数组做这样的题真不容易，用后缀数组就感觉是一件非常纠结的事情了。
这个题的解法还是那种模式化的思路。把N个字符串连接成一个，注意中间加不出现在任何一个字符串中的分隔符，然后建立sa数组和height数组等。最后二分答案，根据答案，即子串的长度对height数组进行分组，分组的思路还是罗穗骞论文里面例3的思路，即从到后枚举height数组，把连续大于等于答案的值放做一组，一旦小于答案那么就是新的分组。这个题需要找到一些分组，其中的后缀是能够出现在N个原串中，这个分组的公共前缀就是sa[i]开始的nMid个字符了(nMid是二分时候获得的子串长度)。由于这个题需要按字典序输出多个满足要求的子串，所以麻烦了点。需要在Check函数里面记录这些子串，而且输出答案的时候需要排序，再unique，由于是按height数组的顺序查找的，而sa[i]已经排好序了，所以排序答案的过程可以省略，但是必须unique。想下Check函数里面遍历height数组的过程就知道可能出现重复的子串。。。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 110;
const int MAX_L = 1010;
const int MAX = MAX_N * MAX_L;
int nAns;
char szStr[MAX_L];
char szAns[MAX][MAX_L];
char* pszAns[MAX];
int nNum[MAX];
int nLoc[MAX];
bool bVis[MAX_N];
int sa[MAX], rank[MAX], height[MAX];
int wa[MAX], wb[MAX], wv[MAX], wd[MAX];
bool CmpStr(const char* pszOne, const char* pszTwo)
{
    return strcmp(pszOne, pszTwo) < 0;
}
bool EqualStr(const char* pszOne, const char* pszTwo)
{
    return strcmp(pszOne, pszTwo) == 0;
}
int cmp(int* r, int a, int b, int l)
{
    return r[a] == r[b]  r[a + l] == r[b + l];
}
//倍增算法,r为待匹配数组,n为总长度,m为字符串范围
void da(int* r, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;

    for (i = 0; i < m; ++i) wd[i] = 0;
    for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
    for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;

    for (j = 1, p = 1; p < n; j *= 2, m = p)
    {
        for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
        for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

        for (i = 0; i < n; ++i) wv[i] = x[y[i]];
        for (i = 0; i < m; ++i) wd[i] = 0;
        for (i = 0; i < n; ++i) wd[wv[i]]++;
        for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];

        swap(x, y);
        for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
        {
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
        }
    }
}
//求height数组
void calHeight(int* r, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; height[rank[i++]] = k)
    {
        if (k) --k;
        for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
    }
}
bool Check(int nMid, int nN, int nK)
{
    int nCnt = 0;
    int nNo = 0;

    memset(bVis, false, sizeof(bVis));
    for (int i = 1; i <= nN; ++i)
    {
        if (height[i] < nMid)
        {
            nCnt = 0;
            memset(bVis, false, sizeof(bVis));
        }
        else
        {
            if (!bVis[nLoc[sa[i - 1]]])
            {
                ++nCnt;
                bVis[nLoc[sa[i - 1]]] = true;
            }
            if (!bVis[nLoc[sa[i]]])
            {
                ++nCnt;
                bVis[nLoc[sa[i]]] = true;
            }
            if (nCnt == nK)
            {
                for (int j = 0; j < nMid; ++j)
                {
                    szAns[nNo][j] = nNum[sa[i] + j];
                }
                szAns[nNo][nMid] = 0;
                ++nNo;
                nCnt = 0;
            }
        }
    }

    if (nNo > 0) nAns = nNo;
    return nNo > 0;
}
int main()
{
    int nN;
    bool bFirst = true;

    while (scanf("%d", &nN), nN)
    {
        if (bFirst) bFirst = false;
        else putchar('\n');

        int nEnd = 300;
        int nP = 0;
        for (int i = 0; i < nN; ++i)
        {
            scanf("%s", szStr);
            int nLen = strlen(szStr);
            for (int j = 0; j < nLen; ++j)
            {
                nNum[nP] = szStr[j];
                nLoc[nP++] = i;
            }
            nNum[nP] = nEnd;
            nLoc[nP++] = nEnd++;
        }
        nNum[nP] = 0;

        if (nN == 1)
        {
            printf("%s\n\n", szStr);
            continue;
        }
        da(nNum, nP + 1, 500);//500是估计的字符集大小
        calHeight(nNum, nP);

        int nLeft = 1, nRight = strlen(szStr);
        int nTemp = 0, nMid;
        int nK = nN / 2 + 1;
        nAns = 0;
        while (nLeft <= nRight)
        {
            nMid = (nLeft + nRight) >> 1;
            if (Check(nMid, nP, nK))
            {
                nTemp = nMid;
                nLeft = nMid + 1;
            }
            else nRight = nMid - 1;
        }
        if (nTemp == 0)
        {
            printf("?\n");
        }
        else
        {
            for (int i = 0; i < nAns; ++i)
            {
                pszAns[i] = szAns[i];
            }
            //sort(pszAns, pszAns + nAns, CmpStr);
            nAns = unique(pszAns, pszAns + nAns, EqualStr) - pszAns;
            for (int i = 0; i < nAns; ++i)
            {
                printf("%s\n", pszAns[i]);
            }
        }
    }

    return 0;
}

poj 1226 Substrings 后缀数组

发表于 2012-10-23 分类于算法，算法题阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

求N个字符串最长的公共子串。这题数据比较水，暴力第一个字符串的子串也可以过。初学后缀数组，有很多不明白的东西，此题后缀数组的代码在网上也是一把抓。
说实话我确实还不懂后缀数组，但是后缀数组太强大了，只能硬着头皮照着葫芦画瓢了。贴下代码方便以后查阅吧。。。
感觉后缀数组的应用最主要的还是height数组，看懂倍增算法排序后缀已经非常困难了。然后再理解height数组怎么用也不是一件容易的事情。然后貌似height数组最关键的用法是枚举某一个长度的子串时候，比如长度为k，能够用这个k对height数组进行分组，这个罗穗骞的论文里面有个求不重叠最长重复子串的例子说明了这个height数组分组的思路，不过我现在还是不怎么理解。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
const int MAX_L = MAX_N * MAX_N;
char szStr[MAX_N];
int nNum[MAX_L];
int nLoc[MAX_L];
bool bVisit[MAX_N];
int sa[MAX_L], rank[MAX_L], height[MAX_L];
int wa[MAX_L], wb[MAX_L], wv[MAX_L], wd[MAX_L];

int cmp(int* r, int a, int b, int l)
{
    return r[a] == r[b]  r[a + l] == r[b + l];
}

//倍增算法,r为待匹配数组,n为总长度,m为字符串范围
void da(int* r, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;

    for (i = 0; i < m; ++i) wd[i] = 0;
    for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
    for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;

    for (j = 1, p = 1; p < n; j *= 2, m = p)
    {
        for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
        for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

        for (i = 0; i < n; ++i) wv[i] = x[y[i]];
        for (i = 0; i < m; ++i) wd[i] = 0;
        for (i = 0; i < n; ++i) wd[wv[i]]++;
        for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];

        swap(x, y);
        for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
        {
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
        }
    }
}

//求height数组
void calHeight(int* r, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; height[rank[i++]] = k)
    {
        if (k) --k;
        for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
    }
}

bool Check(int nMid, int nLen, int nN)
{
    int nCnt = 0;

    memset(bVisit, false, sizeof(bVisit));
    for (int i = 2; i <= nLen; ++i)
    {
        if (nMid > height[i])
        {
            nCnt = 0;
            memset(bVisit, false, sizeof(bVisit));
            continue;
        }
        if (!bVisit[nLoc[sa[i - 1]]])
        {
            bVisit[nLoc[sa[i - 1]]] = true;
            ++nCnt;
        }
        if (!bVisit[nLoc[sa[i]]])
        {
            bVisit[nLoc[sa[i]]] = true;
            ++nCnt;
        }
        if (nCnt == nN) return true;
    }

    return false;
}

int main()
{
    int nT;

    scanf("%d", &nT);
    while (nT--)
    {
        int nN;
        int nEnd = 300;
        int nP = 0;
        scanf("%d", nN);
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%s", szStr);
            char* pszStr;
            for (pszStr = szStr; *pszStr; ++pszStr)
            {
                nLoc[nP] = i;
                nNum[nP++] = *pszStr;
            }
            nLoc[nP] = nEnd;
            nNum[nP++] = nEnd++;

            reverse(szStr, szStr + strlen(szStr));
            for (pszStr = szStr; *pszStr; ++pszStr)
            {
                nLoc[nP] = i;
                nNum[nP++] = *pszStr;
            }
            nLoc[nP] = nEnd;
            nNum[nP++] = nEnd++;
        }
        nNum[nP] = 0;

        da(nNum, nP + 1, nEnd);
        calHeight(nNum, nP);

        int nLeft = 1, nRight = strlen(szStr), nMid;
        int nAns = 0;
        while (nLeft <= nRight)
        {
            nMid = (nLeft + nRight) / 2;
            if (Check(nMid, nP, nN))
            {
                nLeft = nMid + 1;
                nAns = nMid;
            }
            else nRight = nMid - 1;
        }
        printf("%d\n", nAns);
    }

    return 0;
}

poj 3691 DNA repair AC自动机 + dp

发表于 2012-10-21 分类于算法，算法题阅读次数： Valine：
本文字数： 3k 阅读时长 ≈ 3 分钟

题意是给定一系列模式串。然后给出一个文本串，问至少改变文本串里面多少个字符可以使文本串不包含任何一个模式串。
还是先建立Trie图，然后在Trie图上面进行dp。dp的思路也不是很复杂。dp[i][j]的意思是长度为i的文本串需要改变dp[i][j]个字符顺利到达状态j。需要注意的是长度为i的时候，对应的字符串中的第i-1个字符。刚开始一直没发现这个bug。而且注意中途不能转移到匹配成功的状态上去，多加几个条件控制即可了。。。转移方程，dp[i][j] = min(dp[i][j], dp[i-1][nNext] + szText[i-1] != k)，其中nNext是从状态j可以转移到的非匹配成功的状态，k代表的当前边的权。

代码如下：

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 61;
const int MAX_L = 31;
const int MAX_D = 4;
const int INF = 1110;
char chHash[256];
char szPat[MAX_L];

void InitHash()
{
    chHash['A'] = 0;
    chHash['G'] = 1;
    chHash['C'] = 2;
    chHash['T'] = 3;
}

struct Trie
{
    Trie* fail;
    Trie* next[MAX_D];
    bool flag;
    int no;
};
int nP;
Trie* pRoot;
Trie tries[MAX_N * MAX_L];

Trie* NewNode()
{
    memset(tries[nP], 0, sizeof(Trie));
    tries[nP].no = nP;
    return tries[nP++];
}

void InitTrie(Trie* pRoot)
{
    nP = 0;
    pRoot = NewNode();
}

void Insert(Trie* pRoot, char* pszPat)
{
    Trie* pNode = pRoot;
    while (*pszPat)
    {
        int idx = chHash[*pszPat];
        if (pNode->next[idx] == NULL)
        {
            pNode->next[idx] = NewNode();
        }
        pNode = pNode->next[idx];
        ++pszPat;
    }
    pNode->flag = true;
}

void BuildAC(Trie* pRoot)
{
    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);

    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();

        for (int i = 0; i < MAX_D; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front->fail;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                front->next[i]->flag |= front->next[i]->fail->flag;
                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front == pRoot? pRoot : front->fail->next[i];
            }
        }
    }
}

int nChange[INF][INF];
char szText[INF];

int Solve()
{
    int nLen = strlen(szText);
    for (int i = 0; i <= nLen; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            nChange[i][j] = INF;
        }
    }

    int i, j, k;
    nChange[0][0] = 0;
    for (i = 1; i <= nLen; ++i)
    {
        for (j = 0; j < nP; ++j)
        {
            if (tries[j].flag) continue;
            if (nChange[i - 1][j] == INF) continue;
            for (k = 0; k < MAX_D; ++k)
            {
                int nNext = tries[j].next[k] - tries;
                if (tries[nNext].flag) continue;
                //trie是边权树,所以i是从1到len,而且当前字符是szText[i-1]
                int nTemp = nChange[i - 1][j] + (k != chHash[szText[i - 1]]);
                nChange[i][nNext] = min(nChange[i][nNext], nTemp);
            }
        }
    }

    int nAns = INF;
    for (i = 0; i < nP; ++i)
    {
        if (!tries[i].flag)
            nAns = min(nAns, nChange[nLen][i]);
    }
    return nAns == INF? -1 : nAns;
}

int main()
{
    int nN;
    int nCase = 1;

    InitHash();
    while (scanf("%d", &nN), nN)
    {
        InitTrie(pRoot);
        while (nN--)
        {
            scanf("%s", szPat);
            Insert(pRoot, szPat);
        }
        BuildAC(pRoot);
        scanf("%s", szText);
        printf("Case %d: %d\n", nCase++, Solve());
    }

    return 0;
}

poj 1625 Censored! AC自动机 + DP + 大数加法

发表于 2012-10-20 分类于算法，算法题阅读次数： Valine：
本文字数： 4.1k 阅读时长 ≈ 4 分钟

这个题与poj2778dna sequence解法基本一致。只是这个题的答案没有取模，而且文本串不太长。问题是不取模的话就只能输出实际的答案了，就只能用大数了。
而且用大数的话，再用矩阵冥可能就会超时之类的。
这类题还可以用除矩阵冥外的另外一种解法，就是直接dp即可。二维状态，第一维代表文本串长度，第二维代表在AC自动机中的状态。比如dp[i][j]代表长度为i的文本串，转移到Trie图中节点j时候满足不包含任何模式串的答案。剩下的是如何转移状态。转移的话也是考虑next指针数组，设next = tries[j].next[k]，那么有dp[i+1][next] =dp[i+1][next] + dp[i][j]，从0到字母集合大小N枚举k即可。
这个题有一个易错的地方，就是字母集合可能是ascii码在128到256的范围内。而char的范围可能是-128到127或者0到255，这个是根据编译器不同的。所以，直接用字符串数组读入数据后需要再处理下。可以直接将每个字符加128后再处理。
另外，getchar返回的是int，但是与gets之类的函数获得的值的差别也不是那么确定的了。觉得getchar除了对eof之外其余都返回正值。但是，如果char是有符号的话，scanf或者gets之类得到的char数组里面可能就包含负值了。。。
这个可以生成随机文件，再用getchar读入并用%d输出其返回值验证下。验证程序如下：注释掉的部分是生成随机文件的部分。

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char ch;
    freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    int nNum = 100;
    int nCh;
    do
    {
        printf("%d\n", nCh = getchar());
    }
    while (nCh != EOF);
    /*while (nNum--)
    {
        putchar(rand() % 256);
    }*/

    return 0;
}

该题的代码如下：

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_D = 256;
const int MAX_N = 51;
const int MAX_M = 51;
const int MAX_P = 11;
struct Trie
{
    Trie* fail;
    Trie* next[MAX_D];
    int no;
    bool flag;
};
Trie tries[MAX_P * MAX_P];
int nP;
int nN, nM;
Trie* pRoot;
int nHash[MAX_D];
char szPat[MAX_M];

Trie* NewNode()
{
    memset(tries[nP], 0, sizeof(Trie));
    tries[nP].no = nP;
    return tries[nP++];
}

void InitTrie(Trie* pRoot)
{
    nP = 0;
    pRoot = NewNode();
}

void Insert(Trie* pRoot, char* pszPat)
{
    Trie* pNode = pRoot;
    while (*pszPat)
    {
        int idx = nHash[*pszPat];
        if (pNode->next[idx] == NULL)
        {
            pNode->next[idx] = NewNode();
        }
        pNode = pNode->next[idx];
        ++pszPat;
    }
    pNode->flag = true;
}

void BuildAC(Trie* pRoot)
{
    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);

    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();

        for (int i = 0; i < nN; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                front->next[i]->flag |= front->next[i]->fail->flag;
                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front->fail->next[i];
            }
        }
    }
}

const int MAX_L = 200;
struct BigInt
{
    int nD[MAX_L];
    BigInt()
    {
        Clear();
    }
    void Clear()
    {
        memset(nD, 0, sizeof(nD));
    }

    void Print()
    {
        int i = MAX_L - 1;
        while (!nD[i] && i)--i;
        while (i >= 0)
        {
            putchar(nD[i] + '0');
            --i;
        }
    }
    int operator[](int idx) const
    {
        return nD[idx];
    }

    int operator[](int idx)
    {
        return nD[idx];
    }
};
BigInt bi[MAX_M][MAX_D];

BigInt operator+(const BigInt one, const BigInt two)
{
    BigInt ret;

    for (int i = 0, nAdd = 0; i < MAX_L; ++i)
    {
        ret[i] = one[i] + two[i] + nAdd;
        nAdd = ret[i] / 10;
        ret[i] %= 10;
    }

    return ret;
}

void Solve()
{
    BigInt ans;
    for (int i = 0; i <= nM; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            bi[i][j].Clear();
        }
    }
    bi[0][0][0] = 1;

    for (int i = 1; i <= nM; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            if (tries[j].flag) continue;
            for (int k = 0; k < nN; ++k)
            {
                int nNext = tries[j].next[k] - tries;
                if (tries[nNext].flag == false)
                {
                    bi[i][nNext] = bi[i][nNext] + bi[i - 1][j];
                }
            }
        }
    }

    for (int i = 0; i < nP; ++i)
    {
        ans = ans + bi[nM][i];
    }
    ans.Print();
    printf("\n");
}

int main()
{
    int nT;

    while (scanf("%d%d%d%*c", &nN, &nM, &nT) == 3)
    {
        int nCh;
        int nTmp = 0;
        memset(nHash, 0, sizeof(nHash));
        while (nCh = getchar(), nCh != '\n')
        {
            if (!nHash[nCh])
            {
                nHash[nCh] = nTmp++;
            }
        }
        InitTrie(pRoot);
        while (nT--)
        {
            gets(szPat);
            Insert(pRoot, szPat);
        }
        printf("1");
        BuildAC(pRoot);
        printf("2");
        Solve();
    }

    return 0;
}

poj 1509 Glass Beads 字符串最小表示

发表于 2012-10-19 分类于算法，算法题阅读次数： Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

赤裸裸的字符串最小表示题。所谓字符串最小表示指的是给定一个字符串，假设其可以循环移位，问循环左移多少位能够得到最小的字符串。
算法即是周源的最小表示法，搜索可以找到相关论文和ppt。
该算法其实也不是太复杂，思路可以这样理解。假设原字符串为s，设s1 = s + s; s2 = s1循环左移1位;现在处理s1和s2，实际写程序的时候可以通过下标偏移和取模得到s1和s2，而并不需要生成。
处理过程是这样的，设i和j分别指向s1和s2的开头。我们的目的是找到这样的i和j，假设k是s的长度，满足条件s1[i,i+k-1] = s2[j,j+k-1] 并且s1[i,i+k-1] 是所有满足条件的字符串中最小的字符串，如果有多个这样的s1[i,i+k-1] 那么我们希望i最小。
其实这个算法主要是做了一个优化，从而把时间搞成线性的。比如，对于当前的i和j，我们一直进行匹配，也就是s1[i,i+k] = s2[j,j+k] 一直满足，突然到了一个位置s1[i+k] != s2[j+k]了，现在我们需要改变i和j了。但是，我们不能只是++i或者++j。而是根据s1[i+k]>s2[j+k]的话i =i + k + 1，否则j = j + k + 1。这样的瞬移i或者j就能够保证复杂度是线性的了。
问题是如何证明可以这样的瞬移。其实，说穿了也很简单。因为s1[i,i+k - 1] = s2[j,j+k -1]是满足的，只是到了s1[i+k]和s2[j+k]才出现问题了。假如s1[i+k]>s2[j+k]，那么我们改变i为区间[i+1,i+k]中任何一个值m都不可能得到我们想要的答案，这是因为我们总可以在s2中找到相应的比s1[m,m+k-1]小的字符串s2[j+m-i,j+m-i+k-1]，因为有s1[i+k]>s2[j+k]。同样对于s1[i+k]<s2[j+k]的情况。
文字可能描述的不是很清楚。看PPT能够根据图进行分析。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

int GetMin(string str)
{
    int nSize = str.size();
    int i = 0, j = 1, k = 0;

    while (i < nSize && j < nSize && k < nSize)
    {
        char chDif = str[(i + k) % nSize]
                     - str[(j + k) % nSize];
        if (!chDif) ++k;
        else
        {
            if (chDif > 0) i = i + k + 1;
            else j = j + k + 1;
            if (i == j) ++j;
            k = 0;
        }
    }
    return min(i, j);
}

int main()
{
    string str;
    int nN;

    scanf("%d", &nN);
    while (nN--)
    {
        cin >> str;
        printf("%d\n", GetMin(str) + 1);
    }

    return 0;
}