• <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>

            poj 1625 Censored! AC自動機 + DP + 大數加法

               這個題與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];
                }
                
                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 on 2012-10-20 21:01 yx 閱讀(643) 評論(0)  編輯 收藏 引用 所屬分類: 字符串

            <2011年12月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久棈精品久久久久久噜噜| 热久久这里只有精品| 人人妻久久人人澡人人爽人人精品 | 2021国内久久精品| 午夜天堂精品久久久久| 97久久国产亚洲精品超碰热| 国产精品美女久久久久AV福利| 国产精品99久久久久久猫咪 | 久久国产精品二国产精品| 久久九九久精品国产| 久久午夜无码鲁丝片| 国产精品免费久久久久电影网| 思思久久99热免费精品6| 久久亚洲欧美国产精品| 国产精品九九久久免费视频| 日产精品99久久久久久| 久久亚洲精品无码播放| 久久人人爽人人爽人人AV东京热| 7国产欧美日韩综合天堂中文久久久久| 一级a性色生活片久久无| 99久久免费国产精精品| 久久久久se色偷偷亚洲精品av| 久久夜色精品国产亚洲| 久久久久无码精品国产| 久久婷婷是五月综合色狠狠| 狠狠久久综合伊人不卡| 国产午夜久久影院| 日产精品99久久久久久| 久久热这里只有精品在线观看| 久久精品18| 久久av高潮av无码av喷吹| 亚洲欧美精品伊人久久| 久久精品人人做人人爽电影| 亚洲精品tv久久久久久久久| 久久国内免费视频| 亚洲另类欧美综合久久图片区| 国产精品99久久精品爆乳| 999久久久国产精品| 麻豆精品久久久一区二区| 色综合久久最新中文字幕| 久久亚洲精品中文字幕三区|