POJ 1625 Cinnsored(AC自動機＋DP)

2192 ワード

ACM--題解まとめ注意しますデータ構造--AC自動機 practice アゲイン ★★★

POJ 1625 Cinnsored(AC自動機＋DP)
http://poj.org/problem?id=1625
件名:
特定のN文字からなるP個のテンプレートと長さMをあげます.この特定のN個の文字からなる長いM字のテキスト列はいずれのテンプレートを含んでいませんか?M<=50
分析:
  M<=50なので、直接DPを使って、行列べき乗を計算しません.本題はUVA 11468に似ています.
http://blog.csdn.net/u013480600/article/details/23294375
  d[i][j]=xは現在i号ノードにあり、j歩が歩いて、そして接尾語のノードを経ない場合の総数をxとします.
  初期値d[i][0]=1.iは非単語ノードである.
  d[i][j]=sum(d[k][j-1]において、iからkまで歩くことができ、iとkは共に接尾語のノードではない.
  最後に私たちが求めているのはd[0][m]です.(本解法では、メモリーを使って検索することができます.私たちはd[i][j]のすべての依存項d[k][j-1]を分かりやすいからです.
  このように押してもいいです.
  令d[i][j]=xは現在i点にあり、既にj距離を歩いている場合の総数がxであることを示す.
  d[i][j]=sum(d[k][J-1])はkからiまで歩いてもいいし、kとiは非単語ノードです.
  初期値はd[0][0]=1です.他は全部0です.その後、スクロール配列で送ります.(本ノードでは、n［i］［j］のすべての依存項d［k］［j−1］が分からないので、配達リフレッシュのみを使用することができます.)
ACコード:1 A

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxnode=100+20;
int sigma_size;//    
struct AC_Automata
{
    int ch[maxnode][50+20];
    int match[maxnode];
    int f[maxnode];
    map mp;
    int sz;
    void init()
    {
        sz=1;
        memset(ch[0],0,sizeof(ch[0]));
        match[0]=f[0]=0;
        mp.clear();
    }
    void insert(char *s)
    {
        int n=strlen(s),u=0;
        for(int i=0;i q;
        for(int i=0;i=1;i--)
            if(ans[i])
            break;
        for(;i>=0;i--)
            printf("%d",ans[i]);
        putchar('
');
    }
    return 0;
}

spring boot開発において、jsではthymeleafという表記が使われています.

Middlegen-Hiberna-r 5マッピングファイルの使用でエラーが発生しました.