博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
AC 自动机
阅读量：5998 次
发布时间：2019-06-20

本文共 23656 字，大约阅读时间需要 78 分钟。

// begin {AC auto machine}const int MAXN_NODE = 5e5 + 7;const int MAXN_CHAR = 128;int ch[MAXN_NODE][MAXN_CHAR], fail[MAXN_NODE], val[MAXN_NODE],    last[MAXN_NODE], sz;inline int idx(char c) {return (int)c;}void insert(char *s, int v) {  int u = 0, n = strlen(s);  for(int i = 0; i < n; ++i) {    int c = idx(s[i]);    if(!ch[u][c]) {      memset(ch[sz], 0, sizeof(ch[sz]));      //val[sz] = 0;      ch[u][c] = sz++;    }    u = ch[u][c];  }  val[u] = v;}std::queue
    
     q;void get_fail() {  fail[0] = 0;  for(int c = 0; c < MAXN_CHAR; ++c) {    int u = ch[0][c];    if(u) {fail[u] = 0; q.push(u), last[u] = 0;}  }  // BFS  while(!q.empty()) {    int r = q.front(); q.pop();    for(int c = 0; c < MAXN_CHAR; ++c) {      int u = ch[r][c];      if(!u) {ch[r][c] =  ch[fail[r]][c]; continue;}      q.push(u);      int v = fail[r];      while(v && !ch[v][c]) v = fail[v];      fail[u] = ch[v][c];      last[u] = val[fail[u]] ? fail[u] : last[fail[u]];    }  }}void print(int j) {  if(j) {    //printf("%d:%d\n",j,val[j]);    print(last[j]);    ans[val[j]] ++;  }}void find(char *T) {  int n = strlen(T), j = 0;  for(int i = 0; i < n; ++i) {    int c = idx(T[i]);    j = ch[j][c];    if(val[j])  print(j);    else if(last[j]) print(last[j]);  }}void init() {  sz = 1;  memset(ch[0], 0, sizeof(ch[0]));  memset(val, 0, sizeof(val));}// end {AC auto machine}

下面代码针对频繁调用 print 进行了优化，没有立即沿suffix link 更新，而是最后自底向根root更新统计值

// begin {ac-automation}const int MAXN = 3e5 + 7;const int SIGMA_SIZE = 26;struct ac_automation {  struct node {int next[SIGMA_SIZE], fail, val;};  node nod[MAXN];  int length, pos[MAXN], st[MAXN], top;  inline void init() {    length = top = 0; newNode();  }  inline int newNode() {    node &p = nod[length];    p.val = p.fail = 0;    memset(p.next, 0, SIGMA_SIZE * 4);    return length++;  }  inline int idx(char c) {return c - 'a';}  void insert(char *s, int id) {    int cur = 0, k ;    for(; *s; ++s) {      k = idx(s[0]);      node &p = nod[cur];      if(!p.next[k]) p.next[k] = newNode();      cur = p.next[k];    }    pos[id] = cur;  }  std::queue
    
     Q;  void get_fail() {    int cur = 0;    for(register int i = 0; i < SIGMA_SIZE; ++i) {      node &p = nod[cur];      if(p.next[i]) Q.push(p.next[i]);    }    while(!Q.empty()) {      cur = Q.front(); Q.pop();      for(int i = 0; i < SIGMA_SIZE; ++i) {        node &p = nod[cur];        if(p.next[i]) {          int &e = p.next[i], &j = p.fail;          nod[e].fail = nod[j].next[i];          Q.push(e);          st[++top] = e;        } else p.next[i] = nod[p.fail].next[i];      }    }  }  void find(char *s) {    int now = 0;    for(; *s; ++s) {      int k = idx(s[0]);      now = nod[now].next[k];      nod[now].val ++;    }    int tmp = top, p;    while(tmp) {      p = st[tmp];      nod[nod[p].fail].val += nod[p].val;      tmp --;    }  }};// end {ac-automation}

LightOJ 1427 Substring Frequency (II)

题目链接：

给出的模板串会有重复，记录每个串在 \(Trie\) 中的位置 pos , \(Trie\) 中节点统计有次数 \(val\) 输出即可

#include 
    
     #include 
     
      #include 
      
       #include 
       
        // begin {ac-automation}const int MAXN = 3e5 + 7;const int SIGMA_SIZE = 26;struct ac_automation {  struct node {int next[SIGMA_SIZE], fail, val;};  node nod[MAXN];  int length, pos[MAXN], st[MAXN], top;  inline void init() {    length = top = 0; newNode();  }  inline int newNode() {    node &p = nod[length];    p.val = p.fail = 0;    memset(p.next, 0, sizeof(p.next));    return length++;  }  inline int idx(char c) {return c - 'a';}  void insert(char *s, int id) {    int cur = 0, k ;    for(; *s; ++s) {      k = idx(s[0]);      node &p = nod[cur];      if(!p.next[k]) p.next[k] = newNode();      cur = p.next[k];    }    pos[id] = cur;  }  std::queue
        
         Q;  void get_fail() {    int cur = 0;    for(register int i = 0; i < SIGMA_SIZE; ++i) {      node &p = nod[cur];      if(p.next[i]) Q.push(p.next[i]);    }    while(!Q.empty()) {      cur = Q.front(); Q.pop();      for(int i = 0; i < SIGMA_SIZE; ++i) {        node &p = nod[cur];        if(p.next[i]) {          int &e = p.next[i], &j = p.fail;          nod[e].fail = nod[j].next[i];          Q.push(e);          st[++top] = e;        } else p.next[i] = nod[p.fail].next[i];      }    }  }  void find(char *s) {    int now = 0;    for(; *s; ++s) {      int k = idx(s[0]);      now = nod[now].next[k];      nod[now].val ++;    }    int tmp = top, p;    while(tmp) {      p = st[tmp];      nod[nod[p].fail].val += nod[p].val;      tmp --;    }  }};// end {ac-automation}ac_automation ac;const int MAX_t = 1e6 + 7;char t[MAX_t], s[500 + 7];int main() {  int T, n; scanf("%d", &T);  for(int i = 0; i < T; ++i) {    ac.init();    scanf("%d", &n); getchar();    gets(t);    for(int j = 0; j < n; ++j) {      gets(s); ac.insert(s, j + 1);    }    ac.get_fail();    ac.find(t);    printf("Case %d:\n", i + 1);    for(int j = 0; j < n; ++j)      printf("%d\n", ac.nod[ac.pos[j + 1]].val);  }  return 0;}

HDU-2896 病毒侵袭

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         std::bitset<500+7>vis;// begin{Ac_Automation}const int max_node = 5e5 + 7;const int sigma_size = 128;int ch[max_node][sigma_size], val[max_node], sz;int fail[max_node], last[max_node];inline int idx(char c) {return (int)c;}void insert(char *s, int v = 1) {  int u = 0, n = strlen(s);  for(int i = 0; i < n; ++i) {    int c = idx(s[i]);    if(!ch[u][c]) {      memset(ch[sz], 0, sizeof(ch[sz]));      //val[sz] = 0;      ch[u][c] = sz++;    }    u = ch[u][c];  }  val[u] = v;}std::queue
         
          q;void get_fail() { fail[0] = 0; for(int c = 0; c < sigma_size; ++c) { int u = ch[0][c]; if(u) {fail[u] = 0; q.push(u), last[u] = 0;} } // BFS while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c < sigma_size; ++c) { int u = ch[r][c]; if(!u) {ch[r][c] = ch[fail[r]][c]; continue;} q.push(u); int v = fail[r]; while(v && !ch[v][c]) v = fail[v]; fail[u] = ch[v][c]; last[u] = val[fail[u]] ? fail[u] : last[fail[u]]; } }}void print(int j) { if(j) { //printf("%d:%d\n",j,val[j]); print(last[j]); vis[val[j]] = true;; }}void find(char *T) { int n = strlen(T), j = 0; for(int i = 0; i < n; ++i) { int c = idx(T[i]); j = ch[j][c]; if(val[j]) print(j); else if(last[j]) print(last[j]); }}void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); memset(val, 0, sizeof(val));}// end{Ac_Automation}char s[10000007];void solve() { init(); int n; scanf("%d", &n); getchar(); for(int i = 0; i < n; i++) {gets(s); insert(s, i + 1);} get_fail(); int ret = 0; scanf("%d", &n); getchar(); for(int i = 0; i < n; ++i) { gets(s);vis.reset();find(s); if(vis.any()) { printf("web %d:", i + 1); ret++; for(int j = 0; j < 500; ++j) { if(vis[j+1]) printf(" %d", j+1); } puts(""); } } printf("total: %d\n", ret);}int main() {solve(); return 0;}

POJ - 2778 DNA Sequence

#pragma comment(linker, "/STACK:36777216")//#pragma GCC optimize ("O2")#define LOCAL//#include "testlib.h"#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         //#include 
                          
                           //#include 
                           
                            //#include 
                            
                             using namespace std;#define REP(i, n) for (int i=0;i
                             
                              =a;--i)#define REP_1(i, n) for (int i=1;i<=n;++i)#define FOR_1(i, a, b) for (int i=a;i<=b;++i)#define DWN_1(i, b, a) for (int i=b;i>=a;--i)#define REP_C(i, n) for (int n____=n,i=0;i
                              
                               =a____;--i)#define REP_N(i, n) for (i=0;i
                               
                                =a;--i)#define REP_1_C(i, n) for (int n____=n,i=1;i<=n____;++i)#define FOR_1_C(i, a, b) for (int b____=b,i=a;i<=b____;++i)#define DWN_1_C(i, b, a) for (int a____=a,i=b;i>=a____;--i)#define REP_1_N(i, n) for (i=1;i<=n;++i)#define FOR_1_N(i, a, b) for (i=a;i<=b;++i)#define DWN_1_N(i, b, a) for (i=b;i>=a;--i)#define REP_C_N(i, n) for (int n____=(i=0,n);i
                                
                                 =a____;--i)#define REP_1_C_N(i, n) for (int n____=(i=1,n);i<=n____;++i)#define FOR_1_C_N(i, a, b) for (int b____=(i=a,b);i<=b____;++i)#define DWN_1_C_N(i, b, a) for (int a____=(i=b,a);i>=a____;--i)#define ECH(it, A) for (__typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it)#define rECH(it, A) for (__typeof((A).rbegin()) it=(A).rbegin(); it != (A).rend(); ++it)#define REP_S(i, str) for (char*i=str;*i;++i)#define REP_L(i, hd, suc) for (int i=hd;i;i=suc[i])#define REP_G(i, u) REP_L(i,hd[u],suc)#define REP_SS(x, s) for (int x=s;x;x=(x-1)&s)#define DO(n) for ( int ____n = n; ____n-->0; )#define REP_2(i, j, n, m) REP(i, n) REP(j, m)#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)#define ALL(A) A.begin(), A.end()#define LLA(A) A.rbegin(), A.rend()#define CPY(A, B) memcpy(A, B, sizeof(A))#define INS(A, P, B) A.insert(A.begin() + P, B)#define ERS(A, P) A.erase(A.begin() + P)#define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())#define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())#define CTN(T, x) (T.find(x) != T.end())#define SZ(A) int((A).size())#define PB push_back#define MP(A, B) make_pair(A, B)#define PTT pair
                                 
                                  #define Ts *this#define rTs return Ts#define fi first#define se second#define re real()#define im imag()#define Rush for(int ____T=int(RD()); ____T--;)#define Display(A, n, m) { \REP(i, n){ \REP(j, m-1) cout << A[i][j] << " "; \cout << A[i][m-1] << endl; \} \}#define Display_1(A, n, m) { \REP_1(i, n){ \REP_1(j, m-1) cout << A[i][j] << " "; \cout << A[i][m] << endl; \} \}typedef long long LL;//typedef long double DB;typedef double DB;typedef unsigned uint;typedef unsigned long long ULL;typedef vector
                                  
                                    VI;typedef vector
                                   
                                     VC;typedef vector
                                    
                                      VS;typedef vector
                                     
                                       VL;typedef vector
                                      
                                        VF;typedef set
                                       
                                         SI;typedef set
                                        
                                          SS;typedef map
                                         
                                           MII;typedef map
                                          
                                            MSI;typedef pair
                                           
                                             PII;typedef pair
                                            
                                              PLL;typedef vector
                                             
                                               VII;typedef vector
                                              
                                                VVI;typedef vector
                                               
                                                 VVII;template
                                                
                                                  inline T& RD(T &);template
                                                 
                                                   inline void OT(const T &);//inline int RD(){int x; return RD(x);}inline LL RD() {LL x; return RD(x);}inline DB& RF(DB &);inline DB RF() {DB x; return RF(x);}inline char* RS(char *s);inline char& RC(char &c);inline char RC();inline char& RC(char &c) {scanf(" %c", &c); return c;}inline char RC() {char c; return RC(c);}//inline char& RC(char &c){c = getchar(); return c;}//inline char RC(){return getchar();}template
                                                  
                                                    inline T& RDD(T &);inline LL RDD() {LL x; return RDD(x);}template
                                                   
                                                     inline T0& RD(T0 &x0, T1 &x1) {RD(x0), RD(x1); return x0;}template
                                                    
                                                      inline T0& RD(T0 &x0, T1 &x1, T2 &x2) {RD(x0), RD(x1), RD(x2); return x0;}template
                                                     
                                                       inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {RD(x0), RD(x1), RD(x2), RD(x3); return x0;}template
                                                      
                                                        inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}template
                                                       
                                                         inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}template
                                                        
                                                          inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}template
                                                         
                                                           inline void OT(const T0 &x0, const T1 &x1) {OT(x0), OT(x1);}template
                                                          
                                                            inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {OT(x0), OT(x1), OT(x2);}template
                                                           
                                                             inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {OT(x0), OT(x1), OT(x2), OT(x3);}template
                                                            
                                                              inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4) {OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}template
                                                             
                                                               inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5) {OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}template
                                                              
                                                                inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6) {OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}inline char& RC(char &a, char &b) {RC(a), RC(b); return a;}inline char& RC(char &a, char &b, char &c) {RC(a), RC(b), RC(c); return a;}inline char& RC(char &a, char &b, char &c, char &d) {RC(a), RC(b), RC(c), RC(d); return a;}inline char& RC(char &a, char &b, char &c, char &d, char &e) {RC(a), RC(b), RC(c), RC(d), RC(e); return a;}inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f) {RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}inline DB& RF(DB &a, DB &b) {RF(a), RF(b); return a;}inline DB& RF(DB &a, DB &b, DB &c) {RF(a), RF(b), RF(c); return a;}inline DB& RF(DB &a, DB &b, DB &c, DB &d) {RF(a), RF(b), RF(c), RF(d); return a;}inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e) {RF(a), RF(b), RF(c), RF(d), RF(e); return a;}inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f) {RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g) {RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}inline void RS(char *s1, char *s2) {RS(s1), RS(s2);}inline void RS(char *s1, char *s2, char *s3) {RS(s1), RS(s2), RS(s3);}template
                                                               
                                                                inline T0& RDD(T0&a, T1&b) {RDD(a), RDD(b); return a;}template
                                                                
                                                                 inline T1& RDD(T0&a, T1&b, T2&c) {RDD(a), RDD(b), RDD(c); return a;}template
                                                                 
                                                                   inline void RST(T &A) {memset(A, 0, sizeof(A));}template
                                                                  
                                                                    inline void FLC(T &A, int x) {memset(A, x, sizeof(A));}template
                                                                   
                                                                     inline void CLR(T &A) {A.clear();}template
                                                                    
                                                                      inline void RST(T0 &A0, T1 &A1) {RST(A0), RST(A1);}template
                                                                     
                                                                       inline void RST(T0 &A0, T1 &A1, T2 &A2) {RST(A0), RST(A1), RST(A2);}template
                                                                      
                                                                        inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {RST(A0), RST(A1), RST(A2), RST(A3);}template
                                                                       
                                                                         inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}template
                                                                        
                                                                          inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}template
                                                                         
                                                                           inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}template
                                                                          
                                                                            inline void FLC(T0 &A0, T1 &A1, int x) {FLC(A0, x), FLC(A1, x);}template
                                                                           
                                                                             inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {FLC(A0, x), FLC(A1, x), FLC(A2, x);}template
                                                                            
                                                                              inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}template
                                                                             
                                                                               inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}template
                                                                              
                                                                                inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}template
                                                                               
                                                                                 inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}template
                                                                                
                                                                                  inline void CLR(priority_queue
                                                                                 
                                                                                  , less
                                                                                  
                                                                                    > &Q) {while(!Q.empty()) Q.pop();}template
                                                                                   
                                                                                     inline void CLR(priority_queue
                                                                                    
                                                                                     , greater
                                                                                     
                                                                                       > &Q) {while(!Q.empty()) Q.pop();}template
                                                                                      
                                                                                        inline void CLR(stack
                                                                                       
                                                                                         &S) {while(!S.empty()) S.pop();}template
                                                                                        
                                                                                          inline void CLR(queue
                                                                                         
                                                                                           &Q) {while(!Q.empty()) Q.pop();}template
                                                                                          
                                                                                            inline void CLR(T0 &A0, T1 &A1) {CLR(A0), CLR(A1);}template
                                                                                           
                                                                                             inline void CLR(T0 &A0, T1 &A1, T2 &A2) {CLR(A0), CLR(A1), CLR(A2);}template
                                                                                            
                                                                                              inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {CLR(A0), CLR(A1), CLR(A2), CLR(A3);}template
                                                                                             
                                                                                               inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}template
                                                                                              
                                                                                                inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}template
                                                                                               
                                                                                                 inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}template
                                                                                                
                                                                                                  inline void CLR(T &A, int n) {REP(i, n) CLR(A[i]);}template
                                                                                                 
                                                                                                   inline bool EPT(T &a) {return a.empty();}template
                                                                                                  
                                                                                                    inline T& SRT(T &A) {sort(ALL(A)); return A;}template
                                                                                                   
                                                                                                     inline T& SRT(T &A, C B) {sort(ALL(A), B); return A;}template
                                                                                                    
                                                                                                      inline T& RVS(T &A) {reverse(ALL(A)); return A;}template
                                                                                                     
                                                                                                       inline T& UNQQ(T &A) {A.resize(unique(ALL(A)) - A.begin()); return A;}template
                                                                                                      
                                                                                                        inline T& UNQ(T &A) {SRT(A); return UNQQ(A);}/** Constant List .. **/ //{const int MOD = 1e5;//int(1e9) + 7;//const int MOD = 19901013;const int INF = 0x3f3f3f3f;const LL INFF = 0x3f3f3f3f3f3f3f3fLL;const DB EPS = 1e-9;const DB OO = 1e20;const DB PI = acos(-1.0); //M_PI;const int dx[] = { -1, 0, 1, 0};const int dy[] = {0, 1, 0, -1};//}/** Add On .. **/ //{// <<= '0. Nichi Joo ., //{template
                                                                                                       
                                                                                                         inline bool checkMin(T &a, const T b) {return b < a ? a = b, 1 : 0;}template
                                                                                                        
                                                                                                          inline bool checkMax(T &a, const T b) {return a < b ? a = b, 1 : 0;}template 
                                                                                                         
                                                                                                           inline bool checkUpd(T& a, const T b, C c) {return c(b, a) ? a = b, 1 : 0;}template
                                                                                                          
                                                                                                            inline T min(T a, T b, T c) {return min(min(a, b), c);}template
                                                                                                           
                                                                                                             inline T max(T a, T b, T c) {return max(max(a, b), c);}template
                                                                                                            
                                                                                                              inline T min(T a, T b, T c, T d) {return min(min(a, b), min(c, d));}template
                                                                                                             
                                                                                                               inline T max(T a, T b, T c, T d) {return max(max(a, b), max(c, d));}template
                                                                                                              
                                                                                                                inline T min(T a, T b, T c, T d, T e) {return min(min(min(a, b), min(c, d)), e);}template
                                                                                                               
                                                                                                                 inline T max(T a, T b, T c, T d, T e) {return max(max(max(a, b), max(c, d)), e);}template
                                                                                                                
                                                                                                                  inline T sqr(T a) {return a * a;}template
                                                                                                                 
                                                                                                                   inline T cub(T a) {return a * a * a;}template
                                                                                                                  
                                                                                                                    inline T ceil(T x, T y) {return (x - 1) / y + 1;}template
                                                                                                                   
                                                                                                                     T abs(T x) {return x > 0 ? x : -x;}inline int sgn(DB x) {return x < -EPS ? -1 : x > EPS;}inline int sgn(DB x, DB y) {return sgn(x - y);}inline DB cos(DB a, DB b, DB c) {return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);}inline DB cot(DB x) {return 1. / tan(x);};inline DB sec(DB x) {return 1. / cos(x);};inline DB csc(DB x) {return 1. / sin(x);};//}// <<= '2. Number Theory .,//{namespace NT {#define gcd __gcdinline LL lcm(LL a, LL b) {return a * b / gcd(a, b);}inline void INC(int &a, int b) {a += b; if(a >= MOD) a -= MOD;}inline int sum(int a, int b) {a += b; if(a >= MOD) a -= MOD; return a;}/* 模数两倍刚好超 int 时。 inline int sum(uint a, int b){a += b; a %= MOD;if (a < 0) a += MOD; return a;} inline void INC(int &a, int b){a = sum(a, b);} */inline void DEC(int &a, int b) {a -= b; if(a < 0) a += MOD;}inline int dff(int a, int b) {a -= b; if(a < 0) a += MOD; return a;}inline void MUL(int &a, int b) {a = (LL)a * b % MOD;}//inline int pdt(int a, int b){return (LL)a * b % MOD;}inline int pdt(int x, int y) { int ret; __asm__ __volatile__("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(x), "b"(y), "c"(MOD)); return ret;}inline int gcd(int m, int n, int &x, int &y) { x = 1, y = 0; int xx = 0, yy = 1, q; while(1) { q = m / n, m %= n; if(!m) {x = xx, y = yy; return n;} DEC(x, pdt(q, xx)), DEC(y, pdt(q, yy)); q = n / m, n %= m; if(!n) return m; DEC(xx, pdt(q, x)), DEC(yy, pdt(q, y)); }}inline int sum(int a, int b, int c) {return sum(a, sum(b, c));}inline int sum(int a, int b, int c, int d) {return sum(sum(a, b), sum(c, d));}inline int pdt(int a, int b, int c) {return pdt(a, pdt(b, c));}inline int pdt(int a, int b, int c, int d) {return pdt(pdt(a, b), pdt(c, d));}inline int pow(int a, LL b) { int c(1); while(b) { if(b & 1) MUL(c, a); MUL(a, a), b >>= 1; } return c;}template
                                                                                                                    
                                                                                                                      inline T pow(T a, LL b) { T c(1); while(b) { if(b & 1) c *= a; a *= a, b >>= 1; } return c;}template
                                                                                                                     
                                                                                                                       inline T pow(T a, int b) { return pow(a, (LL)b);}inline int _I(int b) { int a = MOD, x1 = 0, x2 = 1, q; while(1) { q = a / b, a %= b; if(!a) return x2; DEC(x1, pdt(q, x2)); q = b / a, b %= a; if(!b) return x1; DEC(x2, pdt(q, x1)); }}inline void DIV(int &a, int b) {MUL(a, _I(b));}inline int qtt(int a, int b) {return pdt(a, _I(b));}struct Int { int val; operator int() const {return val;} Int(int _val = 0): val(_val) { val %= MOD; if(val < 0) val += MOD; } Int(LL _val): val(_val) { _val %= MOD; if(_val < 0) _val += MOD; val = _val; } Int& operator +=(const int& rhs) {INC(val, rhs); rTs;} Int operator +(const int& rhs) const {return sum(val, rhs);} Int& operator -=(const int& rhs) {DEC(val, rhs); rTs;} Int operator -(const int& rhs) const {return dff(val, rhs);} Int& operator *=(const int& rhs) {MUL(val, rhs); rTs;} Int operator *(const int& rhs) const {return pdt(val, rhs);} Int& operator /=(const int& rhs) {DIV(val, rhs); rTs;} Int operator /(const int& rhs) const {return qtt(val, rhs);} Int operator-()const {return MOD - *this;}};} using namespace NT;//}// <<= '7 Matrix Theory ..//namespace MT {const int N = 100;int n = 0;typedef int rec ;struct matrix { rec d[N][N]; void init(rec e = 0) {RST(d); if(e)REP(i, n) d[i][i] = e;} matrix(rec e = 0) {init(e);} matrix operator * (const matrix &rhs)const { matrix res; // REP(i,j,k,n,n,n) res.d[i][j] += d[i][k]*rhs.d[k][j]; REP_2(i, j, n, n) { LL tmp = 0; REP(k, n) tmp += (LL)d[i][k] * rhs.d[k][j];; res.d[i][j] = tmp % MOD; } return res; } matrix operator *= (const matrix &rhs) { (*this) = (*this) * rhs; } inline int res() { int res = 0; REP(i, n) INC(res, d[0][i]); return res; } inline matrix pow_sum(const matrix &a, ULL nn) { matrix t; REP_2(i, j, n, n) t.d[i][j] = t.d[i][j + n] = a.d[i][j]; FOR_C(i, n, n * 2) t.d[i][i] = 1; n <<= 1; t = pow(t, (LL)nn), n >>= 1; REP_2(i, j, n, n) t.d[i][j] = t.d[i][j + n]; return t; } template
                                                                                                                      
                                                                                                                        T pow_sum(T a, ULL nn) { int _n = n; n = 1; matrix t; t.d[0][0] = a; t = pow_sum(t, nn), n = _n; return t.d[0][0]; }};};/** I/O Accelerator Interface .. **/ //{#define g (c=getchar())#define d isdigit(g)#define p x=x*10+c-'0'#define n x=x*10+'0'-c#define pp l/=10,p#define nn l/=10,ntemplate
                                                                                                                       
                                                                                                                         inline T& RD(T &x) { char c; while(!d); x = c - '0'; while(d)p; return x;}template
                                                                                                                        
                                                                                                                          inline T& RDD(T &x) { char c; while(g, c != '-' && !isdigit(c)); if(c == '-') {x = '0' - g; while(d)n;} else {x = c - '0'; while(d)p;} return x;}inline DB& RF(DB &x) { //scanf("%lf", &x); char c; while(g, c != '-' && c != '.' && !isdigit(c)); if(c == '-')if(g == '.') {x = 0; DB l = 1; while(d)nn; x *= l;} else {x = '0' - c; while(d)n; if(c == '.') {DB l = 1; while(d)nn; x *= l;}} else if(c == '.') {x = 0; DB l = 1; while(d)pp; x *= l;} else {x = c - '0'; while(d)p; if(c == '.') {DB l = 1; while(d)pp; x *= l;}} return x;}#undef nn#undef pp#undef n#undef p#undef d#undef ginline char* RS(char *s) { //gets(s); scanf("%s", s); return s;}LL last_ans; int Case; template
                                                                                                                         
                                                                                                                           inline void OT(const T &x) { //printf("Case #%d: ", ++Case); //printf("%lld\n", x); //printf("%.9f\n", x); printf("%d\n", x); //cout << x << endl; //last_ans = x;}//}/* .................................................................................................................................. */namespace ACM { // Aho-Corasick Automatonconst int L = 11, N = 10 * L, Z = 4;int trans[N][Z], fail[N], cnt[N], Q[N], u, cz, op, tot;char str[L]; int ord[128], n;inline int new_node() { RST(trans[tot]), fail[tot] = cnt[tot] = 0; return tot++;}#define v trans[u][c]#define f trans[fail[u]][c]inline void Build() { cz = op = u = 0; REP(c, Z) if(v) Q[op++] = v; while(cz < op) { u = Q[cz++]; REP(c, Z) if(v) fail[Q[op++] = v] = f, cnt[v] |= cnt[f]; else v = f; }}#define c ord[*cur]inline void Insert() { RS(str), u = 0; REP_S(cur, str) { if(cnt[v]) return ; if(!v) v = new_node(); u = v; } cnt[u] = 1;}#undef c#define u Q[i]#define H failint Run() { op = 0; REP(i, tot) if(!cnt[i]) H[i] = op, Q[op++] = i; MT::n = tot; static MT::matrix A; A.init(); REP_2(i, c, op, Z) if(!cnt[v]) ++A.d[H[u]][H[v]]; return pow(A, n).res();}void Init() { int m; RD(m, n), tot = 0, new_node(); DO(m) Insert(); Build();}} using namespace ACM;int main() { ord['A'] = 0, ord['T'] = 1, ord['G'] = 2, ord['C'] = 3; Init(), OT(Run()); return 0;}

上面是岛娘的代码，真心快呀，改天好好学习下

转载于:https://www.cnblogs.com/Forgenvueory/p/7363515.html

你可能感兴趣的文章
自定义key解决zabbix端口监听取值不准确的问题
查看>>
入门级----黑盒测试、白盒测试、手工测试、自动化测试、探索性测试、单元测试、性能测试、数据库性能、压力测试、安全性测试、SQL注入、缓冲区溢出、环境测试...
查看>>
composer 安装 ubuntu 12.04
查看>>
微服务（二）hystrix
查看>>
Performing a thread dump in Linux or Windows--reference
查看>>
推荐系统中常用算法 以及优点缺点对比
查看>>
cocos2d-x v3.2环境配置(现在3.x版本号可以配置该)
查看>>
穷举法解决旅行商问题
查看>>
括号配对问题
查看>>
Oracle自学笔记（一）
查看>>
利用5w1h写出高效的git commit
查看>>
用div和css样式控制页面布局
查看>>
Python自定义库文件路径
查看>>
Get和Post的区别
查看>>
Redis--优化
查看>>
JSTL截取字符串以及格式化时间
查看>>
Bugtags 使用技巧之 setUserData
查看>>
Go语言标准库之JSON编解码
查看>>
使用windows search 搜索文件和文件夹（一）
查看>>
“江苏科技”背后有哪些大咖倾力参与？
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-01 16:27:51   当前IP: 18.190.239.189   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我