青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(653) 評論(0)  編輯 收藏 引用 所屬分類: 字符串

<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

導航

統計

公告

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

me

好友

同學

網友

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            一区二区亚洲欧洲国产日韩| 免费短视频成人日韩| 欧美日韩国产三区| 正在播放亚洲一区| 亚洲综合色激情五月| 国产一区二区三区奇米久涩| 久久男人资源视频| 欧美成人亚洲成人| 夜夜躁日日躁狠狠久久88av| 亚洲夜间福利| 在线观看日韩av电影| 亚洲美女视频网| 国产伦一区二区三区色一情| 久久亚洲国产精品一区二区 | 西瓜成人精品人成网站| 亚洲欧美在线磁力| 亚洲国内欧美| 亚洲免费一区二区| 亚洲国产精品99久久久久久久久| 亚洲免费观看在线观看| 国内一区二区三区| 日韩视频―中文字幕| 激情欧美一区二区三区在线观看| 91久久综合| 国产一区二区三区在线观看精品 | 亚洲精品美女久久7777777| 国产美女精品免费电影| 亚洲国产一区二区精品专区| 国产精品久久波多野结衣| 久久一区中文字幕| 国产精品麻豆欧美日韩ww| 欧美顶级少妇做爰| 国产一区二区久久精品| 一区二区欧美亚洲| 亚洲国产一区二区三区高清| 午夜精品短视频| 9人人澡人人爽人人精品| 久久香蕉精品| 久久精品视频在线观看| 国产精品xnxxcom| 亚洲国产免费| 亚洲福利在线视频| 久久精品国产一区二区电影 | 影音先锋欧美精品| 亚洲永久视频| 亚洲欧美国产日韩中文字幕| 欧美大片免费久久精品三p | 一区二区三区免费网站| 男人插女人欧美| 久久综合久久久久88| 国产日韩综合| 欧美一级在线亚洲天堂| 亚洲欧美视频在线| 国产精品二区在线| 亚洲视频每日更新| 亚洲免费伊人电影在线观看av| 欧美成人国产| 国产午夜精品美女毛片视频| 亚洲无线一线二线三线区别av| 亚洲特级片在线| 欧美剧在线观看| 亚洲激情午夜| 野花国产精品入口| 欧美色区777第一页| 日韩视频免费观看| 亚洲在线观看视频网站| 欧美日韩蜜桃| 亚洲午夜电影| 久久久精品日韩欧美| 韩国欧美一区| 欧美91精品| 日韩午夜在线播放| 欧美一区二区精美| 精品91在线| 欧美大片网址| 亚洲天堂偷拍| 久久亚洲私人国产精品va| 亚洲电影免费| 欧美激情综合五月色丁香小说| 日韩一区二区福利| 久久gogo国模裸体人体| 在线免费高清一区二区三区| 欧美激情亚洲一区| 亚洲性图久久| 美女视频黄 久久| 一区二区三区四区精品| 国产伦精品一区二区三区高清| 欧美在线观看日本一区| 亚洲国产片色| 欧美一级久久久久久久大片| 在线观看不卡av| 欧美视频第二页| 欧美日韩播放| 亚洲小视频在线观看| 久久久精品一区| 日韩视频二区| 国产亚洲精品成人av久久ww| 女女同性精品视频| 亚洲欧美精品中文字幕在线| 欧美成人午夜剧场免费观看| 一区二区三区四区五区视频| 国产一区二区精品久久91| 欧美顶级少妇做爰| 欧美在线观看视频| 亚洲日本一区二区三区| 久久久久国产精品午夜一区| 日韩视频欧美视频| 好男人免费精品视频| 欧美日韩中字| 久久最新视频| 午夜性色一区二区三区免费视频| 欧美激情精品| 久久精品日韩一区二区三区| 欧美大尺度在线| 亚洲一区三区视频在线观看| 免费看成人av| 久久精品盗摄| 亚洲综合激情| 亚洲精品美女免费| 永久免费视频成人| 国产情人综合久久777777| 欧美体内谢she精2性欧美| 欧美成人四级电影| 久久免费黄色| 久久久久久综合网天天| 亚洲精品综合在线| 影音先锋另类| 精品不卡一区二区三区| 国产婷婷色综合av蜜臀av| 国产精品久久久久久久浪潮网站 | 亚洲欧洲日本国产| 亚洲欧美激情诱惑| 国产精品激情| 欧美国产1区2区| 久久综合网络一区二区| 久久久精品五月天| 久久99在线观看| 欧美亚洲视频在线看网址| 亚洲欧美综合v| 欧美一区二区三区婷婷月色| 欧美一区1区三区3区公司| 午夜精品久久久| 欧美在线不卡视频| 久久久噜噜噜久久狠狠50岁| 久久久久国产一区二区三区四区| 久久久www成人免费毛片麻豆| 欧美在线视频不卡| 久久频这里精品99香蕉| 免费日韩av片| 欧美日韩视频在线第一区| 欧美激情综合色| 欧美三日本三级少妇三2023| 国产精品欧美一区喷水| 国产欧美一区二区精品性| 国产欧美在线| 亚洲国产精品va在线看黑人动漫 | 欧美精品入口| 欧美日韩免费一区| 国产精品国产三级国产专播品爱网| 国产精品毛片大码女人| 国产在线麻豆精品观看| 在线播放日韩| 欧美一区国产二区| 巨胸喷奶水www久久久免费动漫| 欧美激情日韩| 国产美女精品人人做人人爽| 国产综合在线看| 亚洲六月丁香色婷婷综合久久| 亚洲一区二区三区四区中文| 欧美一进一出视频| 免费亚洲电影在线| 在线性视频日韩欧美| 小辣椒精品导航| 欧美国产精品v| 国产欧美精品日韩区二区麻豆天美| 在线精品福利| 亚洲一区二区免费| 麻豆精品视频在线观看视频| 亚洲看片免费| 久久久精品性| 久久综合狠狠综合久久综青草| 久久精品亚洲热| 欧美日韩高清在线观看| 国内精品久久久久影院薰衣草| 999亚洲国产精| 久久亚洲一区二区三区四区| 亚洲裸体俱乐部裸体舞表演av| 久久成人国产| 国产精品久久久久高潮| 亚洲麻豆视频| 毛片基地黄久久久久久天堂| 亚洲一区二区三区在线视频| 欧美成人久久| 国精品一区二区三区| 亚洲欧美日韩一区在线观看| 亚洲国产导航| 久久先锋资源| 极品尤物av久久免费看| 久久国产成人| 精品va天堂亚洲国产|