• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            2012年10月25日

            poj 3264 Balanced Lineup St算法建立Rmq

               ST算法可以說就是個(gè)二維的動(dòng)態(tài)規(guī)劃,黑書上有解釋。
               
            #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;
            }

            posted @ 2012-10-25 19:29 yx 閱讀(485) | 評(píng)論 (0)編輯 收藏

            2012年10月24日

            hdu 3068 最長(zhǎng)回文 Manacher算法

               該題就是求一個(gè)字符串的最長(zhǎng)回文子串,就是一個(gè)滿足本身是回文的最長(zhǎng)的子串。
               該題貌似可以用后綴數(shù)組和擴(kuò)展kmp做,但是好像后綴數(shù)組貌似會(huì)tle,改學(xué)了下
            一個(gè)專門的叫Manacher算法的東西。。。
               這又是一個(gè)線性改良算法。找到有篇文章寫的不錯(cuò),鏈接如下:
            http://www.felix021.com/blog/read.php?2040
               該算法說起來也不是太復(fù)雜,比較容易看懂的那種,當(dāng)然是接觸過其它字符串算法
            的前提下了。記得以前就看了看,硬是沒看懂,想不到現(xiàn)在這么快就明白了。
               該算法需要額外的O(N)空間。說起來是空間換時(shí)間吧。
               大概的思路是先預(yù)處理字符串,使其成為一個(gè)長(zhǎng)度一定為偶數(shù)的串。而且第一個(gè)字符
            是'$',假設(shè)'$'沒有在原串出現(xiàn)過。然后再在原來的每個(gè)字符前面加上'#',最后再加個(gè)
            '#'。比如,abc就變成了$#a#b#c#。現(xiàn)在再對(duì)新的字符串進(jìn)行處理。
               開一個(gè)新的數(shù)組nRad[MAX],nRad[i]表示新串中第i個(gè)位置向左邊和向右邊同時(shí)擴(kuò)展
            并且保持對(duì)稱的最大距離。如果求出了nRad數(shù)組后,有一個(gè)結(jié)論,nRad[i]-1恰好表示原串
            對(duì)應(yīng)的位置能夠擴(kuò)展的回文子串長(zhǎng)度。這個(gè)的證明,應(yīng)該比較簡(jiǎn)單,因?yàn)樾麓旧鲜窃?br />的2倍了,而且新串每一個(gè)有效字符兩側(cè)都有插入的#,這個(gè)找個(gè)例子看下就知道是這樣了。
               最重要的是如何求出nRad數(shù)組。
               求這個(gè)數(shù)組的算法也主要是利用了一些間接的結(jié)論優(yōu)化了nRad[i]的初始化值。比如我們求
            nRad[i]的時(shí)候,如果知道了i以前的nRad值,而且知道了前面有一個(gè)位置id,能夠最大的向
            兩邊擴(kuò)展距離max。那么有一個(gè)結(jié)論,nRad[i] 能夠初始化為min(nRad[2*id - i], max - i),
            然后再進(jìn)行遞增。關(guān)鍵是如何證明這個(gè),這個(gè)的證明,對(duì)照?qǐng)D片就很清楚了。
               證明如下:
               當(dāng) mx - i > P[j] 的時(shí)候,以S[j]為中心的回文子串包含在以S[id]為中心的回文子串中,由于 i 和 j 對(duì)稱,
            以S[i]為中心的回文子串必然包含在以S[id]為中心的回文子串中,所以必有 P[i] = P[j],見下圖。
                
               
               當(dāng) P[j] > mx - i 的時(shí)候,以S[j]為中心的回文子串不完全包含于以S[id]為中心的回文子串中,但是基于
            對(duì)稱性可知,下圖中兩個(gè)綠框所包圍的部分是相同的,也就是說以S[i]為中心的回文子串,其向右至少會(huì)
            擴(kuò)張到mx的位置,也就是說 P[i] >= mx - i。至于mx之后的部分是否對(duì)稱,就只能老老實(shí)實(shí)去匹配了。
               
                  這個(gè)就說明得很清楚了。。。

                  代碼如下:
            #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;
            }

            posted @ 2012-10-24 20:55 yx 閱讀(1288) | 評(píng)論 (0)編輯 收藏

            poj 3294 Life Forms 后綴數(shù)組求至少出現(xiàn)在K個(gè)字符串中的最長(zhǎng)公共子串

               此題就是給出N個(gè)字符串,然后求一個(gè)最長(zhǎng)的子串,它至少出現(xiàn)在N/2+1個(gè)字符串中,
            如果有多個(gè)這樣的子串,按字典序輸出,如果沒有這樣的子串,輸出?。
               此題是羅穗騫論文里面的例11,他有講述具體的解法。要用后綴數(shù)組做這樣的題真不
            容易,用后綴數(shù)組就感覺是一件非常糾結(jié)的事情了。
               這個(gè)題的解法還是那種模式化的思路。把N個(gè)字符串連接成一個(gè),注意中間加不出現(xiàn)在
            任何一個(gè)字符串中的分隔符,然后建立sa數(shù)組和height數(shù)組等。
               最后二分答案,根據(jù)答案,即子串的長(zhǎng)度對(duì)height數(shù)組進(jìn)行分組,分組的思路還是羅穗
            騫論文里面例3的思路,即從到后枚舉height數(shù)組,把連續(xù)大于等于答案的值放做一組,
            一旦小于答案那么就是新的分組。這個(gè)題需要找到一些分組,其中的后綴是能夠出現(xiàn)在N個(gè)原
            串中,這個(gè)分組的公共前綴就是sa[i]開始的nMid個(gè)字符了(nMid是二分時(shí)候獲得的子串長(zhǎng)度)。
               由于這個(gè)題需要按字典序輸出多個(gè)滿足要求的子串,所以麻煩了點(diǎn)。需要在Check函數(shù)里面
            記錄這些子串,而且輸出答案的時(shí)候需要排序,再unique,由于是按height數(shù)組的順序查找的,
            而sa[i]已經(jīng)排好序了,所以排序答案的過程可以省略,但是必須unique。想下Check函數(shù)里面
            遍歷height數(shù)組的過程就知道可能出現(xiàn)重復(fù)的子串。。。

               代碼如下:
            #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為待匹配數(shù)組,n為總長(zhǎng)度,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數(shù)組
            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是估計(jì)的字符集大小
                    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;
            }

            posted @ 2012-10-24 15:57 yx 閱讀(1272) | 評(píng)論 (0)編輯 收藏

            2012年10月23日

            poj 1226 Substrings 后綴數(shù)組

               求N個(gè)字符串最長(zhǎng)的公共子串。這題數(shù)據(jù)比較水,暴力第一個(gè)字符串的子串也可以過。
            初學(xué)后綴數(shù)組,有很多不明白的東西,此題后綴數(shù)組的代碼在網(wǎng)上也是一把抓。
               說實(shí)話我確實(shí)還不懂后綴數(shù)組,但是后綴數(shù)組太強(qiáng)大了,只能硬著頭皮照著葫蘆畫瓢了。
            貼下代碼方便以后查閱吧。。。
               感覺后綴數(shù)組的應(yīng)用最主要的還是height數(shù)組,看懂倍增算法排序后綴已經(jīng)非常困難了。
            然后再理解height數(shù)組怎么用也不是一件容易的事情。然后貌似height數(shù)組最關(guān)鍵的用法是
            枚舉某一個(gè)長(zhǎng)度的子串時(shí)候,比如長(zhǎng)度為k,能夠用這個(gè)k對(duì)height數(shù)組進(jìn)行分組,這個(gè)羅穗騫
            的論文里面有個(gè)求不重疊最長(zhǎng)重復(fù)子串的例子說明了這個(gè)height數(shù)組分組的思路,不過我現(xiàn)在
            還是不怎么理解。。。
              
            #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為待匹配數(shù)組,n為總長(zhǎng)度,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數(shù)組
            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, falsesizeof(bVisit));
                for (int i = 2; i <= nLen; ++i)
                {
                    if (nMid > height[i])
                    {
                        nCnt = 0;
                        memset(bVisit, falsesizeof(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;
            }

            posted @ 2012-10-23 21:11 yx 閱讀(542) | 評(píng)論 (0)編輯 收藏

            2012年10月21日

            poj 3691 DNA repair AC自動(dòng)機(jī) + dp

               題意是給定一系列模式串。然后給出一個(gè)文本串,問至少改變文本串里面多少個(gè)字符
            可以使文本串不包含任何一個(gè)模式串。
               還是先建立Trie圖,然后在Trie圖上面進(jìn)行dp。dp的思路也不是很復(fù)雜。dp[i][j]的意思
            是長(zhǎng)度為i的文本串需要改變dp[i][j]個(gè)字符順利到達(dá)狀態(tài)j。需要注意的是長(zhǎng)度為i的時(shí)候,
            對(duì)應(yīng)的字符串中的第i-1個(gè)字符。剛開始一直沒發(fā)現(xiàn)這個(gè)bug。而且注意中途不能轉(zhuǎn)移到
            匹配成功的狀態(tài)上去,多加幾個(gè)條件控制即可了。。。
               轉(zhuǎn)移方程,dp[i][j] = min(dp[i][j], dp[i-1][nNext] + szText[i-1] != k),其中nNext
            是從狀態(tài)j可以轉(zhuǎn)移到的非匹配成功的狀態(tài),k代表的當(dāng)前邊的權(quán)。
               
               代碼如下:
            #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是邊權(quán)樹,所以i是從1到len,而且當(dāng)前字符是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;
            }

            posted @ 2012-10-21 16:53 yx 閱讀(548) | 評(píng)論 (0)編輯 收藏

            2012年10月20日

            poj 1625 Censored! AC自動(dòng)機(jī) + DP + 大數(shù)加法

               這個(gè)題與poj2778dna sequence解法基本一致。只是這個(gè)題的答案沒有取模,
            而且文本串不太長(zhǎng)。問題是不取模的話就只能輸出實(shí)際的答案了,就只能用大數(shù)了。
               而且用大數(shù)的話,再用矩陣冥可能就會(huì)超時(shí)之類的。
               這類題還可以用除矩陣冥外的另外一種解法,就是直接dp即可。
               二維狀態(tài),第一維代表文本串長(zhǎng)度,第二維代表在AC自動(dòng)機(jī)中的狀態(tài)。
               比如dp[i][j]代表長(zhǎng)度為i的文本串,轉(zhuǎn)移到Trie圖中節(jié)點(diǎn)j時(shí)候滿足不包含任何模式串的答案。
            剩下的是如何轉(zhuǎn)移狀態(tài)。轉(zhuǎn)移的話也是考慮next指針數(shù)組,設(shè)next = tries[j].next[k],
            那么有dp[i+1][next] = dp[i+1][next] + dp[i][j],從0到字母集合大小N枚舉k即可。
               這個(gè)題有一個(gè)易錯(cuò)的地方,就是字母集合可能是ascii碼在128到256的范圍內(nèi)。而char
            的范圍可能是-128到127或者0到255,這個(gè)是根據(jù)編譯器不同的。所以,直接用字符串
            數(shù)組讀入數(shù)據(jù)后需要再處理下??梢灾苯訉⒚總€(gè)字符加128后再處理。
               另外,getchar返回的是int,但是與gets之類的函數(shù)獲得的值的差別也不是那么確定的了。
            我覺得getchar除了對(duì)eof之外其余都返回正值。但是,如果char是有符號(hào)的話,scanf或者
            gets之類得到的char數(shù)組里面可能就包含負(fù)值了。。。
               這個(gè)可以生成隨機(jī)文件,再用getchar讀入并用%d輸出其返回值驗(yàn)證下。驗(yàn)證程序如下:
            注釋掉的部分是生成隨機(jī)文件的部分。
            #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];
                }
                
                intoperator[](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;
            }

            posted @ 2012-10-20 21:01 yx 閱讀(635) | 評(píng)論 (0)編輯 收藏

            2012年10月19日

            poj 1509 Glass Beads 字符串最小表示

               赤裸裸的字符串最小表示題。所謂字符串最小表示指的是給定一個(gè)字符串,假設(shè)其可以循環(huán)移
            位,問循環(huán)左移多少位能夠得到最小的字符串。
               算法即是周源的最小表示法,搜索可以找到相關(guān)論文和ppt。
               該算法其實(shí)也不是太復(fù)雜,思路可以這樣理解。假設(shè)原字符串為s,設(shè)s1 = s + s; s2 = s1循
            環(huán)左移1位;現(xiàn)在處理s1和s2,實(shí)際寫程序的時(shí)候可以通過下標(biāo)偏移和取模得到s1和s2,而并不需
            要生成。
               處理過程是這樣的,設(shè)i和j分別指向s1和s2的開頭。我們的目的是找到這樣的i和j,假設(shè)k是s的
            長(zhǎng)度,滿足條件s1[i,i+k-1] = s2[j,j+k-1] 并且s1[i,i+k-1] 是所有滿足條件的字符串中最小的
            字符串,如果有多個(gè)這樣的s1[i,i+k-1] 那么我們希望i最小。
               其實(shí)這個(gè)算法主要是做了一個(gè)優(yōu)化,從而把時(shí)間搞成線性的。比如,對(duì)于當(dāng)前的i和j,我們一直
            進(jìn)行匹配,也就是s1[i,i+k] = s2[j,j+k] 一直滿足,突然到了一個(gè)位置s1[i+k]  != s2[j+k]了,
            現(xiàn)在我們需要改變i和j了。但是,我們不能只是++i或者++j。而是根據(jù)s1[i+k]>s2[j+k]的話i =
            i + k + 1,否則j = j + k + 1。這樣的瞬移i或者j就能夠保證復(fù)雜度是線性的了。
               問題是如何證明可以這樣的瞬移。其實(shí),說穿了也很簡(jiǎn)單。因?yàn)閟1[i,i+k - 1] = s2[j,j+k -1]
            是滿足的,只是到了s1[i+k]和s2[j+k]才出現(xiàn)問題了。假如s1[i+k]>s2[j+k],那么我們改變i為
            區(qū)間[i+1,i+k]中任何一個(gè)值m都不可能得到我們想要的答案,這是因?yàn)槲覀兛偪梢栽趕2中找到相應(yīng)
            的比s1[m,m+k-1]小的字符串s2[j+m-i,j+m-i+k-1],因?yàn)橛衧1[i+k]>s2[j+k]。
               同樣對(duì)于s1[i+k]<s2[j+k]的情況。
               文字可能描述的不是很清楚??碢PT能夠根據(jù)圖進(jìn)行分析。

               代碼如下:
            #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;
            }

            posted @ 2012-10-19 19:44 yx 閱讀(1063) | 評(píng)論 (0)編輯 收藏

            2012年10月18日

            hnu 2243 考研路茫?!獑卧~情結(jié) AC自動(dòng)機(jī)+矩陣冥累加和

               這個(gè)題目更奇葩。據(jù)說是上一個(gè)題的加強(qiáng)版。
               題意是給定M個(gè)模式串,然后給定長(zhǎng)度L,問不超過L的文本至少含有一個(gè)模式的情況的總種數(shù)。

               還是用模式串建立Trie圖,根據(jù)Trie圖建立起路徑長(zhǎng)度為1的矩陣M。
               總情況數(shù)目為26^1+26^2+...+26^L。不含模式串的情況總數(shù)為矩陣N = M^1+M^2+M^3
            +...+M^L的第一行之和??偳闆r數(shù)目減去不含模式串的情況就是答案。
               這里用到了矩陣的一些算法,比如快速冥,還有快速冥求和。但是,我用了操作符重載,最悲劇
            的是重載后的操作符沒有優(yōu)先級(jí),而我還當(dāng)作有優(yōu)先級(jí)的在用,所以悲劇了。。。一直樣例都過不
            去。。。唉,最后才發(fā)現(xiàn)了這個(gè)問題。。。寫了260行左右的代碼,前面的一部分代碼可以當(dāng)作矩
            陣操作的模板了。。。Trie圖的也不錯(cuò),過幾天估計(jì)得打印下來用了。。。

               代碼如下:
            #include <stdio.h>
            #include <string.h>
            #include <queue>
            #include <algorithm>
            using namespace std;

            typedef unsigned long long INT;
            const int MAX_D = 26;
            const int MAX_L = 10;
            const int MAX_N = 10;
            char szPat[MAX_L];

            const int MAX_S = 31;
            struct Matrix
            {
                int nSize;
                INT nD[MAX_S][MAX_S];
                Matrix(int nS)
                {
                    Clear(nS);
                }

                Matrix& operator = (const Matrix& m)
                {
                    nSize = m.nSize;
                    for (int i = 0; i < nSize; ++i)
                    {
                        for (int j = 0; j < nSize; ++j)
                        {
                            nD[i][j] = m.nD[i][j];
                        }
                    }
                    return *this;
                }
                void Clear(int nS)
                {
                    nSize = nS;
                    memset(nD, 0, sizeof(nD));
                }
                void Unit()
                {
                    for (int i = 0; i < nSize; ++i)
                    {
                        for (int j = 0; j < nSize; ++j)
                        {
                            nD[i][j] = (i == j ? 1 : 0);
                        }
                    }
                }
            };

            Matrix operator+(const Matrix& A, const Matrix& B)
            {
                Matrix C(A.nSize);

                for (int i = 0; i < A.nSize; ++i)
                {
                    for (int j = 0; j < A.nSize; ++j)
                    {
                        C.nD[i][j] = A.nD[i][j] + B.nD[i][j];
                    }
                }
                return C;
            }

            Matrix operator*(const Matrix& nA, const Matrix& nB)
            {
                Matrix nC(nB.nSize);
                for (int i = 0; i < nA.nSize; ++i)
                {
                    for (int j = 0; j < nA.nSize; ++j)
                    {
                        for (int k = 0; k < nA.nSize; ++k)
                        {
                            nC.nD[i][j] += nA.nD[i][k] * nB.nD[k][j];
                        }
                    }
                }
                return nC;
            }

            Matrix operator^(Matrix B, INT nExp)
            {
                Matrix ans(B.nSize);

                ans.Unit();
                while (nExp)
                {
                    if (nExp % 2)
                    {
                        ans = ans * B;
                    }
                    B = B * B;
                    nExp >>= 1;
                }
                return ans;
            }

            //求base^1+base^2++base^N
            Matrix SumPowMatrix(Matrix& base, INT nN)
            {
                if (nN == 1)
                {
                    return base;
                }

                Matrix ans = SumPowMatrix(base, nN / 2);
                ans = ans + ((base^(nN / 2)) * ans);//重載運(yùn)算符保證不了優(yōu)先級(jí)
                if (nN % 2)
                {
                    ans = ans + (base^nN);//沒優(yōu)先級(jí)啊,必須加括號(hào),查錯(cuò)2個(gè)小時(shí)了
                }
                return ans;
            }

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

            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 = *pszPat - 'a';
                    if (pNode->next[idx] == NULL)
                    {
                        pNode->next[idx] = NewNode();
                    }
                    pNode = pNode->next[idx];
                    ++pszPat;
                }
                pNode->flag = true;
            }

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

                M.Clear(nP);
                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;
                            if (front->next[i]->fail->flag)
                            {
                                front->next[i]->flag = true;
                            }
                            qt.push(front->next[i]);
                        }
                        else
                        {
                            front->next[i] = front == pRoot? pRoot : front->fail->next[i];
                        }

                        //這里必須要加上front->flag為false的判斷么?加不加會(huì)生成不同的矩陣
                        if (!front->next[i]->flag)
                        {
                            ++M.nD[front->no][front->next[i]->no];
                        }
                    }
                }
            }

            int main()
            {
                int nN;
                INT nL;
                Matrix M(0);

                while (scanf("%d%I64u", &nN, &nL) == 2)
                {
                    InitTrie(pRoot);
                    while (nN--)
                    {
                        scanf("%s", szPat);
                        Insert(pRoot, szPat);
                    }
                    BuildAC(pRoot, M);

                    Matrix tmp(1);
                    tmp.nD[0][0] = 26;
                    tmp = SumPowMatrix(tmp, nL);
                    INT nAns = tmp.nD[0][0];
                    Matrix msum = SumPowMatrix(M, nL);
                    for (int i = 0; i < msum.nSize; ++i)
                    {
                        nAns -= msum.nD[0][i];
                    }
                    printf("%I64u\n", nAns);
                }

                return 0;
            }

            posted @ 2012-10-18 22:02 yx 閱讀(1238) | 評(píng)論 (0)編輯 收藏

            poj 2778 DNA Sequence AC自動(dòng)機(jī)+矩陣快速冥

               題意很簡(jiǎn)單,假定文本集就是A,C,T,G,給定M個(gè)模式串,問你長(zhǎng)度為N的文本不出現(xiàn)這些模式
            串的可能性到底有多少種。。。
               確實(shí)非常不直觀的樣子。。。
               解法是先學(xué)學(xué)AC自動(dòng)機(jī),建立起Trie圖,根據(jù)trie圖可以得到長(zhǎng)度為1的路徑矩陣,然后再快速
            冥得到長(zhǎng)度為N的路徑矩陣。
               說起來都非常糾結(jié),沒學(xué)過AC自動(dòng)機(jī)更加無法理解。學(xué)AC自動(dòng)機(jī)之前據(jù)說得先學(xué)Trie樹和KMP
            才好理解。學(xué)AC自動(dòng)機(jī)搞Trie圖就花費(fèi)了近2天了,然后弄懂這個(gè)題又是一天,好在基本明白了。
               馬上快比賽了,從長(zhǎng)春換到金華也不知道是好是壞。。。還是弱菜啊。。。
               貼下我的Trie圖+快速冥(直接二分了,沒有寫成數(shù)論里面那種算法)...

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

            typedef long long INT;
            const int MOD = 100000;
            const int MAX_P = 100;
            const int MAX_D = 4;
            int nIdx[256];
            char szPat[MAX_P];
            INT nMatrix[MAX_P][MAX_P];
            INT B[MAX_P][MAX_P];
            INT A[MAX_P][MAX_P];

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

            struct Trie
            {
                Trie* fail;
                Trie* next[MAX_D];
                int no;
                bool flag;
                Trie()
                {
                    fail = NULL;
                    memset(next, 0, sizeof(next));
                    no = 0;
                    flag = false;
                }
            };
            Trie tries[MAX_D * MAX_P];
            int nP;
            Trie* pRoot;

            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(char* pszPat)
            {
                Trie* pNode = pRoot;
                
                while (*pszPat)
                {
                    if (pNode->next[nIdx[*pszPat]] == NULL)
                    {
                        pNode->next[nIdx[*pszPat]] = NewNode();
                    }
                    pNode = pNode->next[nIdx[*pszPat]];
                    ++pszPat;
                }
                pNode->flag = true;
            }

            int BuildAC(Trie* pRoot)
            {
                memset(nMatrix, 0, sizeof(nMatrix));
                
                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;
                            if (front->next[i]->fail->flag == true)
                            {
                                front->next[i]->flag = true;
                            }
                            
                            qt.push(front->next[i]);
                        }
                        else
                        {
                            front->next[i] = front == pRoot? pRoot : front->fail->next[i];
                        }
                        
                        if (front->next[i]->flag == false)
                        {
                            nMatrix[front->no][front->next[i]->no]++;
                        }
                    }
                }
                
                return nP;//節(jié)點(diǎn)總個(gè)數(shù)
            }

            void MultyMatrix(INT A[][MAX_P], INT B[][MAX_P], INT C[][MAX_P], int nSize)
            {
                for (int i = 0; i < nSize; ++i)
                {
                    for (int j = 0; j < nSize; ++j)
                    {
                        INT nSum = 0;
                        for (int k = 0; k < nSize; ++k)
                        {
                            nSum = (nSum + A[i][k] * B[k][j]) % MOD;
                        }
                        C[i][j] = nSum;
                    }
                }
            }

            void CopyMatrix(INT A[][MAX_P], INT B[][MAX_P], int nSize)
            {
                for (int i = 0; i < nSize; ++i)
                {
                    for (int j = 0; j < nSize; ++j)
                    {
                        A[i][j] = B[i][j];
                    }
                }
            }

            void MatrixPower(INT M[][MAX_P], int nSize, INT nP)
            {
                if (nP == 1)
                {
                    CopyMatrix(A, M, nSize);
                    return;
                }
                
                MatrixPower(M, nSize, nP / 2);
                MultyMatrix(A, A, B, nSize);
                if (nP % 2)
                {
                    MultyMatrix(B, M, A, nSize);
                }
                else
                {
                    CopyMatrix(A, B, nSize);
                }
            }

            int main()
            {
                INT nM, nN;
                
                InitIdx();
                while (scanf("%I64d%I64d", &nM, &nN) == 2)
                {
                    InitTrie(pRoot);
                    while (nM--)
                    {
                        scanf("%s", szPat);
                        Insert(szPat);
                    }
                    int nSize = BuildAC(pRoot);
                    
                    MatrixPower(nMatrix, nSize, nN);
                    INT nAns = 0;
                    for (int i = 0; i < nSize; ++i)
                    {
                        nAns = (nAns + A[0][i]) % MOD;
                    }
                    printf("%I64d\n", nAns % MOD);
                }
                
                return 0;
            }
               
               

            posted @ 2012-10-18 09:46 yx 閱讀(1216) | 評(píng)論 (0)編輯 收藏

            2012年10月12日

            hnu 10076 Jimmy's Riddles DFA

               句子的語法匹配。這個(gè)用DFA確實(shí)可以很方便做出來,用遞歸判斷之類的應(yīng)該也可以。
               感覺用dfa只需要保證狀態(tài)轉(zhuǎn)換圖對(duì)了,基本上就不會(huì)出bug了,但是其它的方法去匹配
            這種類似正則表達(dá)式的字符串就容易出錯(cuò)多了。

               百度百科的DFA定義如下:
                  英文全稱:Deterministic Finite Automaton, 簡(jiǎn)寫:DFA
              DFA定義:一個(gè)確定的有窮自動(dòng)機(jī)(DFA)M是一個(gè)五元組:M=(K,Σ,f,S,Z)其中
              ① K是一個(gè)有窮集,它的每個(gè)元素稱為一個(gè)狀態(tài);
              ② Σ是一個(gè)有窮字母表,它的每個(gè)元素稱為一個(gè)輸入符號(hào),所以也稱Σ為輸入符號(hào)字母表;
              ③ f是轉(zhuǎn)換函數(shù),是K×Σ→K上的映射,即,如 f(ki,a)=kj,(ki∈K,kj∈K)就意味著,
            當(dāng)前狀態(tài)為ki,輸入符為a時(shí),將轉(zhuǎn)換為下一個(gè)狀態(tài)kj,我們把kj稱作ki的一個(gè)后繼狀態(tài);
              ④ S ∈ K是唯一的一個(gè)初態(tài);
              ⑤ Z⊂K是一個(gè)終態(tài)集,終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。

               該題的狀態(tài)轉(zhuǎn)換圖:
               
               現(xiàn)在再根據(jù)狀態(tài)轉(zhuǎn)換圖,寫一個(gè)模擬轉(zhuǎn)換關(guān)系的匹配就非常方便了。。。
               代碼如下:
            #include <string>
            #include <vector>
            #include <sstream>
            #include <iostream>
            #include <algorithm>
            using namespace std;

            string strNouns[8] =
            {
                "tom", "jerry", "goofy", "mickey",
                "jimmy", "dog", "cat", "mouse"
            };

            bool IsNoun(string& str)
            {
                for (int i = 0; i < 8; ++i)
                {
                    if (str == strNouns[i])
                    {
                        return true;
                    }
                }
                return false;
            }

            bool IsVerb(string& str)
            {
                return str == "hate" || str == "love"
                        || str == "know" || str == "like"
                        || str == "hates" || str == "loves"
                        || str == "knows" || str == "likes"; 
            }

            bool IsArticle(string& str)
            {
                return str == "a" || str == "the";
            }

            bool CheckState(vector<string>& vs)
            {
                if (vs.empty()) return false;
                
                int nState = 0;
                for (int i = 0; i < vs.size(); ++i)
                {
                    //printf("nState:%d, str:%s\n", nState, vs[i].c_str());
                    switch (nState)
                    {
                        case 0:
                            if (IsArticle(vs[i]))
                            {
                                nState = 1;
                                break;
                            }
                            else if (IsNoun(vs[i]))
                            {
                                nState = 2;
                                break;
                            }
                            else
                            {
                                return false;
                            }
                            
                        case 1:
                            if (IsNoun(vs[i]))
                            {
                                nState = 2;
                                break;
                            }
                            else
                            {
                                return false;
                            }
                            
                        case 2:
                            if (vs[i] == "and")
                            {
                                nState = 0;
                                break;
                            }
                            else if (IsVerb(vs[i]))
                            {
                                nState = 3;
                                break;
                            }
                            else
                            {
                                return false;
                            }
                            
                        case 3:
                            if (IsArticle(vs[i]))
                            {
                                nState = 4;
                                break;
                            }
                            else if (IsNoun(vs[i]))
                            {
                                nState = 5;
                                break;
                            }
                            else
                            {
                                return false;
                            }
                            
                        case 4:
                            if (IsNoun(vs[i]))
                            {
                                nState = 5;
                                break;
                            }
                            else
                            {
                                return false;
                            }
                            
                        case 5:
                            if (vs[i] == "and")
                            {
                                nState = 3;
                                break;
                            }
                            else if (vs[i] == ",")
                            {
                                nState = 0;
                                break;
                            }
                            else
                            {
                                return false;
                            }
                    }
                }
                
                return nState == 5;
            }

            int main()
            {
                int nT;
                
                scanf("%d%*c", &nT);
                while (nT--)
                {
                    vector<string> vs;
                    string line, str;
                    
                    getline(cin, line);
                    stringstream ss(line);
                    while (ss >> str)
                    {
                        vs.push_back(str);
                    }
                    printf("%s\n", CheckState(vs) ? "YES I WILL" : "NO I WON'T");
                }
                
                return 0;
            }

            posted @ 2012-10-12 22:14 yx 閱讀(1046) | 評(píng)論 (2)編輯 收藏

            僅列出標(biāo)題  下一頁
            <2025年5月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學(xué)

            網(wǎng)友

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            伊人久久成人成综合网222| 久久久久久午夜成人影院| 久久精品国产欧美日韩| 亚洲中文字幕伊人久久无码| 亚洲国产精品婷婷久久| 亚洲国产天堂久久久久久| 国内精品久久久久久不卡影院| 国产亚洲精久久久久久无码77777| 国产精品久久久久9999| 久久久久久久综合狠狠综合| 国产精品久久久久影院色| 久久青青草原精品国产| 久久综合给合久久国产免费| 久久久久免费视频| 久久久久亚洲av毛片大| 狠狠色丁香久久综合婷婷| 久久久无码精品亚洲日韩京东传媒| 色综合色天天久久婷婷基地| 性欧美大战久久久久久久久| 色综合久久天天综线观看| 久久久久久久综合日本亚洲| 久久精品国产亚洲一区二区| 久久精品国产亚洲欧美| 99久久精品免费国产大片| 久久免费观看视频| 色狠狠久久综合网| 久久综合久久自在自线精品自| 国产成人久久精品一区二区三区| 亚洲精品乱码久久久久久蜜桃图片 | 99久久综合国产精品免费| 亚洲综合婷婷久久| 久久久久国产一级毛片高清板 | 久久久久久精品久久久久| 精品国产99久久久久久麻豆| 久久99国产综合精品| 99久久精品九九亚洲精品| 亚洲午夜精品久久久久久浪潮 | 人人狠狠综合久久亚洲婷婷| 久久青青草原精品国产不卡| 精品国产99久久久久久麻豆 | 色婷婷久久综合中文久久一本|