AC自动机专题总结

AC自动机专题总结（2020.8.6~2020.8.13）

个人对AC自动机的理解:利用字典树构建fail指针，并维护一些字符串的末尾节点的标记的一种字符串方面的算法，题目经常和dp结合。

ac自动机(模板题)

HDU2222
题目大意：给定N个模式串和一个文本串，询问在文本串中有多少模式串出现。
思路：模板题细节及注释见代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const double eps=1e-8;
const int maxn = 1e6+5;      ///输入字符串上限值
const int N = 10000*50 + 5 ; ///结点数上限值
int T;
int n,m;
char s[maxn];
int nxt[N][26],fail[N],flg[N],cnt;
queue<int>q;
void init() ///多组输入所以要初始化
{
    cnt = 0; ///字典树根节点设为0
    memset(nxt,0,sizeof nxt); memset(fail,0,sizeof fail); memset(flg,0,sizeof flg);
}
void Insert(char *s)
{
    int p = 0; ///从根节点开始
    for(int i=0; s[i] ; ++i)
    {
        int c = s[i] - 'a';   ///字符串只有小写字母组成
        if(!nxt[p][c]) nxt[p][c] = ++cnt;
        p = nxt[p][c];
    }
    flg[p]++; ///以p结点为末尾的字符串数加一
}
void Build() ///构建fail指针
{
    for(int c=0;c<26;++c)
    {
        if(nxt[0][c]){
            q.push(nxt[0][c]); ///把从根节点向下走的第一个存在的结点入队
            fail[nxt[0][c]] = 0; ///可省略因为根节点为0
        }
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int c=0;c<26;++c)
        {
            if(nxt[u][c])
            {
                fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]); ///若结点u以字符(c+'a')为边的子结点存在，则用父节点的fail指针更新子节点，并将其入队
            }
            else nxt[u][c] = nxt[fail[u]][c];
        }
    }
}
void Query(char *s)
{
    int p = 0;
    int ans = 0;
    for(int i=0; s[i] ; ++i)
    {
        int c = s[i]-'a';
        p = nxt[p][c];
        for(int j = p; j && flg[j]!=-1 ; j = fail[j])
        {
            if(flg[j]) ans+=flg[j],flg[j]=-1; ///加完之后标记为-1,因为结点p对答案的贡献最多为flg[p]
        }
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%s",s); Insert(s);
        }
        Build();
        scanf("%s",s);
        //for(int i=0;i<=cnt;++i) printf("%d ",fail[i]);
        Query(s);
    }
    return 0;
}

HDU2896
题意: 给定N个病毒特征码和M个网址，询问每个网址中有哪些病毒特征码出现。
思路: 由于是多个文本串（网址），所以每次查询的时候需要初始化vis数组（vis[i]=1表示第i个病毒特征码出现）

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define show(x) std::cerr << #x << "=" << x << std::endl
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int n,m;
int ans = 0;
char t[505][205],s[maxn];
queue<int>q;
struct Automan
{
   int nxt[maxn][128],fail[maxn],idx[maxn],val[maxn],vis[505],tot=0;
   void init()
   {
       tot=0;
       memset(nxt,0,sizeof nxt);memset(fail,0,sizeof fail);memset(idx,0,sizeof idx);
       memset(val,0,sizeof val);memset(cnt,0,sizeof cnt);
   }
   void Insert(char *s,int lens,int id)
   {
       int p = 0;
       for(int i=1;i<=lens;++i)
       {
           int c = s[i];
           if(!nxt[p][c]) nxt[p][c] = ++tot;
           p = nxt[p][c];
       }
       idx[p] = id;
   }
   void Build()
   {
        while(!q.empty()) q.pop();
       for(int c = 0; c < 128; ++c)
       {
           int p = nxt[0][c];
           if(p) {
            q.push(p); fail[p] = 0;
           }
       }
       while(!q.empty())
       {
           int u = q.front(); q.pop();
           for(int c = 0; c < 128; ++c)
           {
               if(nxt[u][c])
               {
                   fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
               }
               else nxt[u][c] = nxt[fail[u]][c];
           }
       }
   }
   void Query(char *t,int lent,int id)
   {
       memset(vis,0,sizeof vis);
       int p = 0;
       bool flg = 0;
       for(int i=1;i<=lent;++i)
       {
           int c = t[i] ;
           p = nxt[p][c];
           for(int j = p; j ; j = fail[j])
           {
               if(idx[j]) {flg = 1; vis[idx[j]]=1;}
           }
       }
       if(!flg) return ;
       ++ans;
       printf("web %d:",id);
       for(int i=1;i<=n;++i)
       {
           if(vis[i]) printf(" %d",i);
       }
       puts("");
   }
}AC;
int main()
{
    AC.init();
    ans = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",t[i]+1);
        AC.Insert(t[i],strlen(t[i]+1),i);
    }
    AC.Build();
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%s",s+1);
        AC.Query(s,strlen(s+1),i);
    }
    printf("total: %d\n",ans);
    return 0;
}

HDU3065
细节：源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。故nxt数组二维得开256

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define show(x) std::cerr << #x << "=" << x << std::endl
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int maxn = 5e4+5;
const int N = 2e6+5;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int n,m;
char t[1005][55],s[N];
queue<int>q;
struct Automan
{
   int nxt[maxn][26],fail[maxn],idx[maxn],cnt[1005],val[maxn],tot=0;
   void init()
   {
       tot = 0;
       for(int i=0;i<maxn;++i) fill(nxt[i],nxt[i]+26,0);
       fill(fail,fail+maxn,0);fill(idx,idx+maxn,0);
       fill(cnt,cnt+5005,0);fill(val,val+maxn,0);

   }
    void Insert(char *s,int lens,int id)
    {
        int p = 0;
        for(int i=1;i<=lens;++i)
        {
            int c = s[i] - 'A';
            if(!nxt[p][c]) nxt[p][c] = ++tot;
            p = nxt[p][c];
        }
        idx[p] = id;
    }
    void Build()
    {
         while(!q.empty()) q.pop();
        for(int c = 0; c < 26; ++c)
        {
            int p = nxt[0][c];
            if(p) {
                q.push(p); fail[p] = 0;
            }
        }
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int c = 0;  c < 26; ++c)
            {

                if(nxt[u][c])
                {
                    fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
                }
                else nxt[u][c] = nxt[fail[u]][c];
            }
        }
    }
    void Query(char *t,int lent)
    {
        int p = 0;
        for(int i=1;i<=lent;++i)
        {
            int c = s[i] - 'A';
            if(c<0 || c>=26) {p = 0; continue;}
            p = nxt[p][c];
            for(int j = p; j ; j = fail[j])
            {
                if(idx[j]) cnt[idx[j]]++;
            }
        }
    }
}AC;
int main()
{
    while(~scanf("%d",&n)){
            AC.init();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",t[i]+1);
        AC.Insert(t[i],strlen(t[i]+1),i);
    }
    AC.Build();
    scanf("%s",s+1);
    AC.Query(s,strlen(s+1));
    for(int i=1;i<=n;++i)
    {
        if(AC.cnt[i])
        {
            printf("%s: %d\n",t[i]+1,AC.cnt[i]);
        }
    }}
    return 0;
}

ZOJ3430
和base64结合的神仙模板题，不会base64得看好久

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define show(x) std::cerr << #x << "=" << x << std::endl
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int maxn = 2e6+5;
const int N = 6e4 + 5;
const int M = 256;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int n,m;
char s[maxn];
unsigned char t[maxn];
struct Automan
{
   int nxt[N][M],fail[N],cnt[N],tot=0;
   bool vis[N];
   void init()
   {
       tot = 0;
       memset(nxt,0,sizeof nxt); memset(fail,0,sizeof fail); memset(cnt,0,sizeof cnt);
   }
   void Insert(unsigned char *s,int lens)
   {
       int p = 0;
       for(int i=1;i<=lens;++i)
       {
           int c = s[i];
           if(!nxt[p][c]) nxt[p][c] = ++tot;
           p = nxt[p][c];
       }
       cnt[p]=1;
   }
   void Build()
   {
       queue<int>q; while(!q.empty()) q.pop();
       for(int c = 0; c<M ; ++c)
       {
           if(nxt[0][c]) {
            q.push(nxt[0][c]), fail[nxt[0][c]] = 0;
           }
       }
       while(!q.empty())
       {
            int u = q.front(); q.pop();
            for(int c = 0; c<M ;++c)
            {
                if(nxt[u][c])
                {
                    fail[nxt[u][c]] = nxt[fail[u]][c] ; q.push(nxt[u][c]);
                }
                else nxt[u][c] = nxt[fail[u]][c] ;
            }
       }
   }
   int Query(unsigned char *t,int lent)
   {
       int p = 0;
       int ans = 0;
       memset(vis,0,sizeof vis);
       for(int i=1;i<=lent;++i)
       {
           int c = t[i];
           p = nxt[p][c];
           for(int j = p; j && !vis[j] ; j = fail[j])
           {
                ans+=cnt[j], vis[j] = 1;
           }
       }
       return ans;
   }
}AC;
int trans(char c)
{
    if(c>='A' && c<='Z') return c-'A';
    if(c>='a' && c<='z') return c-'a'+26;
    if(isdigit(c)) return c-'0'+52;
    if(c=='+') return 62;
    if(c=='/') return 63;
}
int p = 0;
void decode_base64(char *s,int lens) ///自己写的解密
{
    while(s[lens]=='=' && lens>=1) --lens;
    int k = lens/4, i;
    p = 0;
    for(i=1;i<=lens;++i)
    {
        s[i] = trans(s[i]);
    }
    for(i=1;i+3<=lens;i+=4)
    {
        ///s[i~i+3]
        t[++p] = ((s[i]&63)<<2) | ((s[i+1]&48)>>4);
        t[++p] = ((s[i+1]&15)<<4) | ((s[i+2]&60)>>2);
        t[++p] = ((s[i+2]&3)<<6) | (s[i+3]&63);
    }
    if(lens%4==2)
    {
        t[++p] = ((s[i]&63)<<2) | ((s[i+1]&48)>>4);
    }
    if(lens%4==3)
    {
        t[++p] = ((s[i]&63)<<2) | ((s[i+1]&48)>>4);
        t[++p] = ((s[i+1]&15)<<4) | ((s[i+2]&60)>>2);
    }
    //for(i=1;i<=p;++i) printf("%d ",t[i]);puts("");
}
void decode(char *s,int lens) ///别人的解密
{
    p = 0;
    for(int i=0,len=0,x=0;s[i]&&s[i]!='=';++i)
    {
        len+=6;
        x=(x<<6)|trans(s[i]);
        if(len>=8)
        {
            t[++p] =  (x>>(len-8))&0xff;
            len-=8;
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        AC.init();
        for(int i=1;i<=n;++i)
        {
            scanf("%s",s+1);
            decode_base64(s,strlen(s+1));
            AC.Insert(t,p);
        } AC.Build();
        scanf("%d",&m);
        for(int i=1;i<=m;++i)
        {
            scanf("%s",s+1);
            decode_base64(s,strlen(s+1));
            printf("%d\n",AC.Query(t,p));
        }
        printf("\n");
    }
    return 0;
}

ac自动机(和搜索，矩阵快速幂结合的)

HDU3247
题意: 给定n个数据串和m个病毒串，询问串S的最小的长度，使得S包含所有数据串（可overlap）而且存在病毒串
思路： 利用ac自动机存储数据串和病毒串，在数据串在字典树中的末尾节点标记为f[p] = 1<<id,病毒串标记为g[p] = 1，之后利用BFS求出最短长度即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int N = 6e4+2;
const int M =  1025;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int t;
int n,m;
char s[N];
int nxt[N][2],fail[N],f[N],g[N],cnt;
bool vis[N][M];
int ed;
struct node
{
    int i,j,k;
};

void init()
{
    cnt = 0;
    memset(nxt,0,sizeof nxt); memset(fail,0,sizeof fail);
    memset(f,0,sizeof f); memset(g,0,sizeof g);
}
void Insert(char *s,int x,int id)
{
    int p = 0;
    for(int i=0;s[i];++i)
    {
        int c = s[i]-'0';
        if(!nxt[p][c]) nxt[p][c] = ++cnt;
        p = nxt[p][c];
    }
    if(x) f[p] = 1<<id;
    else g[p] = 1;
}
void Build()
{
    queue<int>q;
    for(int i=0;i<2;++i)
    {
        if(nxt[0][i]) q.push(nxt[0][i]),fail[nxt[0][i]] = 0;
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int c = 0; c<2;++c)
        {
           if(nxt[u][c])
           {
               fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
               f[nxt[u][c]] |= f[nxt[fail[u]][c]];
               g[nxt[u][c]] |= g[nxt[fail[u]][c]];
           }
           else nxt[u][c] = nxt[fail[u]][c];
        }
    }
}
void solve()
{
    queue<node>Q;
    memset(vis,0,sizeof vis);
    Q.push({0,0,0}); vis[0][0] = 1;
    int i,j,k;
    while(!Q.empty())
    {
        node p = Q.front(); Q.pop();
        i = p.i, j =p.j, k =p.k;
        if(k == ed)
        {
            printf("%d\n",i);
            break;
        }
        for(int c = 0; c<2;++c)
        {
            int nj = nxt[j][c] , nk = k|f[nj];
            if(g[nj] || vis[nj][nk]) continue;
            Q.push({i+1,nj,nk}), vis[nj][nk] = 1;
        }
    }

    while(!Q.empty()) Q.pop();

}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        if(n==0 && m==0) break;
        for(int i=1;i<=n;++i)
        {
            scanf("%s",s); Insert(s,1,i-1);
        }
        for(int i=1;i<=m;++i)
        {
            scanf("%s",s); Insert(s,0,i);
        }

        Build(); ed = 0;
        for(int i=0;i<=cnt;++i)
        {
            ed|=f[i];
        }
        solve();
    }
    return 0;
}
/*
2 2
1110
0111
101
1001
*/

POJ2778
和矩阵快速幂结合

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int maxn = 2e5+5;
const int N = 205;
const ll mod = 100000;
const int inf = 0x3f3f3f3f;
int t;
int n,m;
char s[15][15];

int get(char c)
{
    if(c=='A') return 0;
    if(c=='G') return 1;
    if(c=='C') return 2;
    if(c=='T') return 3;
}
queue<int>q;
struct Automan
{
    int nxt[N][4],fail[N],flg[N],tot;
    void init()
    {
        tot = 0;
        memset(nxt,0,sizeof nxt);memset(fail,0,sizeof fail); memset(flg,0,sizeof flg);
    }
    void Insert(char *s,int lens)
    {
        int p = 0;
        for(int i=1;s[i];++i)
        {
            int c = get(s[i]);
            if(!nxt[p][c]) nxt[p][c] = ++tot;
            p = nxt[p][c];
        }
        flg[p] = 1;
    }
    void Build()
    {
        while(!q.empty()) q.pop();
        for(int c = 0; c < 4; ++c)
        {
            if(nxt[0][c]){
                q.push(nxt[0][c]); fail[nxt[0][c]] = 0;
            }

        }
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int c = 0; c<4 ;++c)
            {
                if(nxt[u][c]) {
                    fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
                }
                else nxt[u][c] = nxt[fail[u]][c];
                flg[nxt[u][c]] |= flg[nxt[fail[u]][c]];
            }
        }
    }
}AC;
struct Mat
{
    ll a[105][105];
    Mat(){memset(a,0,sizeof a);}
};
Mat operator*(const Mat &A, const Mat &B)
{
    Mat C;
    for(int i=0;i<=AC.tot;++i)
    {
        for(int j=0;j<=AC.tot;++j)
        {
            for(int k=0;k<=AC.tot;++k)
            {
                C.a[i][j] = (C.a[i][j] + A.a[i][k]*B.a[k][j])%mod;
            }
        }
    }
    return C;
}
Mat qmod(Mat A,int b)
{
    Mat I;
    for(int i=0;i<=AC.tot;++i) I.a[i][i] = 1;

    for(;b;b>>=1)
    {
        if(b&1) I = I*A;
        A = A*A;
    }

    return I;
}
int main()
{


    {
        scanf("%d%d",&m,&n);
        AC.init();
        for(int i=1;i<=m;++i)
        {
            scanf("%s",s[i]+1);
            AC.Insert(s[i],strlen(s[i]+1));
        }
        AC.Build();
        Mat A;
        for(int i=0;i<=AC.tot;++i)
        {
            if(AC.flg[i]) continue;
            for(int c=0; c<4; ++c)
            {
                if(AC.flg[AC.nxt[i][c]]) continue;
                A.a[i][AC.nxt[i][c]]++;
            }
        }

        A = qmod(A,n);
        ll ans = 0;
        for(int i=0;i<=AC.tot;++i)
        {
            ans = (ans + A.a[0][i])%mod;
        }
        printf("%lld\n",ans);
    }

    return 0;
}

HDU2243
在上题基础上更加深入

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define show(x) std::cerr << #x << "=" << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps=1e-8;
const int maxn = 65;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int N,L;
char s[10];
int nxt[maxn][26],fail[maxn],flg[maxn],cnt = 0;
queue<int>q;
void init()
{
    cnt = 0;
    memset(nxt,0,sizeof nxt); memset(fail,0,sizeof fail); memset(flg,0,sizeof flg);
}
void Insert(char *s)
{
    int p = 0;
    for(int i=0;s[i];++i)
    {
        int c = s[i]-'a';
        if(!nxt[p][c]) nxt[p][c] = ++cnt;
        p= nxt[p][c];
    }
    flg[p] = 1;
}
void Build()
{
    for(int c = 0; c<26; ++c)
    {
        if(nxt[0][c]) {
            q.push(nxt[0][c]); fail[nxt[0][c]] = 0;
        }
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int c = 0; c<26; ++c)
        {
            if(nxt[u][c]){
                fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
            }
            else nxt[u][c] = nxt[fail[u]][c];
            flg[nxt[u][c]] |= flg[nxt[fail[u]][c]];
        }
    }
}
struct Mat
{
    ull mat[maxn][maxn];
    Mat(){ memset(mat,0,sizeof mat);}

};
Mat operator *(const Mat &A,const Mat &B)
{
    Mat C;
    for(int i=0;i<=60;++i)
    {
        for(int j=0;j<=60;++j)
        {
            for(int k=0;k<=60;++k)
            {
                C.mat[i][j]+=A.mat[i][k]*B.mat[k][j];
            }
        }
    }
    return C;
}
Mat qmod(Mat A,int b)
{
    Mat E; for(int i=0;i<=60;++i) E.mat[i][i] = 1;
    for(;b;b>>=1)
    {
        if(b&1) E = E*A;
        A = A*A;
    }
    return E;
}
int main()
{
    while(~scanf("%d%d",&N,&L))
    {
        init();
        for(int i=1;i<=N;++i)
        {
            scanf("%s",s);
            Insert(s);
        }
        Build();

        Mat P; P.mat[0][0] = 26,P.mat[0][1] = 1, P.mat[1][0] = 0, P.mat[1][1] = 1;
        P = qmod(P,L);

        ull S = P.mat[0][1]*26;

        ///S为长度不超过L的所有单词数
        Mat A;
        for(int i=0;i<=cnt;++i)
        {
            if(flg[i]) continue;
            for(int c = 0; c<26;++c)
            {
                if(flg[nxt[i][c]]) continue;
                A.mat[i][nxt[i][c]]++;
            }
        }
        Mat B = A;
        for(int i=cnt+1;i<=2*cnt+1;++i)
        {
            B.mat[i-cnt-1][i] = 1;
            B.mat[i][i] = 1;
        }

        B = qmod(B,L);
        Mat D;
        for(int i=0;i<=cnt;++i)
        {
            for(int j=0;j<=cnt;++j) D.mat[i][j] = B.mat[i][j+cnt+1];
        }
        D = D*A;
        ull ans =0;
        for(int i=0;i<=cnt;++i)
        {
            ans = ans+D.mat[0][i];
        }
        printf("%llu\n",S-ans);
    }
    return 0;
}
/*
2 2
aa ab
*/

ac自动机(和dp结合的)

HDU4511
题目大意: 从结点1出发要到达结点n，每次只能走比当前结点编号大的点，其中有m条路径不能走，询问到达n结点的最短路

思路: 将每条不能走的路径利用ac自动机存储并标记，之后利用dp求解即可

细节：两点之间的距离会爆ll,直接用double存点坐标即可

初始化
$dp[1][nxt[0][1]] = 0$dp[1][nxt[0][1]]=0
$其余值置为无穷大$其余值置为无穷大

如果idx[nj]未被标记时dp方程,其中c为编号大于i的结点
$dp[c][nj] = min(dp[c][nj],dp[i][j] + dis(c,i))$dp[c][nj]=min(dp[c][nj],dp[i][j]+dis(c,i))
答案
$min(dp[n][j]) (0<=j<=cnt)$min(dp[n][j])(0<=j<=cnt)

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define show(x) std::cerr << #x << "=" << x << std::endl

using namespace std;
typedef long long ll;
const double eps=1e-4;
const int maxn = 2e5+5;
const int mod = 1e9+7;
const int N = 505;
const double inf = DBL_MAX;
int n,m;
int k,path[10];
double x[55],y[55];
int nxt[N][55],fail[N],idx[N],cnt;
int pre[55][N];
double f[55][N];
bitset<55>b[55][N];
queue<int>q;
double dis(int a,int b)
{
    return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
}
void init()
{
    cnt = 0;
    memset(nxt,0,sizeof nxt); memset(fail,0,sizeof fail); memset(idx,0,sizeof idx);
    memset(pre,-1,sizeof pre);
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<N;++j) f[i][j] = inf;
    }
}
void Insert(int id)
{
    int p = 0;
    for(int i=1;i<=k;++i)
    {
        int c = path[i];
        if(!nxt[p][c]) nxt[p][c] = ++cnt;
        p = nxt[p][c];
    }
    idx[p] = id;
}
void Build()
{
    for(int i=1;i<=n;++i)
    {
        if(nxt[0][i])
        {
            q.push(nxt[0][i]); fail[nxt[0][i]] = 0;
        }
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int c=1;c<=n;++c)
        {
            if(nxt[u][c])
            {
                fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
            }
            else nxt[u][c] = nxt[fail[u]][c];
            idx[nxt[u][c]] |= idx[nxt[fail[u]][c]];
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m) )
    {
        if(n==0 && m==0) break;
        init();
        for(int i=1;i<=n;++i)
        {
            scanf("%lf%lf",&x[i],&y[i]);
        }
        for(int i=1;i<=m;++i)
        {
            scanf("%d",&k);
            for(int j=1;j<=k;++j)
            {
                scanf("%d",&path[j]);
            }
            Insert(i);
        }
        Build();

        f[1][nxt[0][1]] = 0;

        for(int i=1;i<n;++i)
        {
            for(int j=0;j<=cnt;++j)
            {
                if(f[i][j]==inf) continue;
                for(int c=i+1;c<=n;++c)
                {
                    int nj = nxt[j][c];
                    double d = dis(i,c);
                    if(!idx[nj] && f[i][j]+d < f[c][nj])
                    {
                        f[c][nj] = f[i][j] + d;
                    }
                }
            }
        }
        double ans = inf;
        for(int i=0;i<=cnt;++i)
        {
            if(f[n][i] == inf) continue;
            //printf("%.2lf\n",f[n][i]);
            ans = min(ans,f[n][i]);
        }
        if(fabs(ans-inf)<=eps) puts("Can not be reached!");
        else printf("%.2lf\n",ans);
    }
    return 0;
}

HDU2825

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double eps=1e-8;
const int maxn = 2e5+5;
const int N = 105;
const int M = 1<<10 + 2;
const int mod = 20090717;
const int inf = 0x3f3f3f3f;
int t;
int n,m,x;
char s[15];
int nxt[N][26],fail[N],flg[N],cnt;
int dp[26][N][M];
queue<int>q;
void init()
{
    cnt = 0;
}
void Insert(char *s,int id)
{
    int p = 0;
    for(int i=0;s[i];++i)
    {
        int c = s[i]-'a';
        if(!nxt[p][c]) nxt[p][c] = ++cnt;
        p = nxt[p][c];
    }
    flg[p] = 1<<id;
}
void Build()
{
    for(int c=0;c<26;++c)
    {
        if(nxt[0][c]) {
            q.push(nxt[0][c]); fail[nxt[0][c]] = 0;
        }
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int c = 0; c<26; ++c)
        {
            if(nxt[u][c]){
                fail[nxt[u][c]] = nxt[fail[u]][c]; q.push(nxt[u][c]);
            }
            else nxt[u][c] = nxt[fail[u]][c];
            flg[nxt[u][c]] |= flg[nxt[fail[u]][c]];
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&x))
    {
        cnt = 0;
        if(n==0 && m==0 && x==0) break;
        for(int i=0;i<m;++i)
        {
            scanf("%s",s);
            Insert(s,i);
        }
        Build();
        int tot = (1<<m);
        dp[0][0][0] = 1;

        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<=cnt;++j)
            {
                for(int k=0;k<tot;++k)
                {
                    if(!dp[i-1][j][k]) continue;
                    for(int c=0;c<26;++c)
                    {
                        int nj = nxt[j][c];
                        int nk = k|flg[nj];
                        dp[i][nj][nk] += dp[i-1][j][k];
                        if(dp[i][nj][nk]>=mod) dp[i][nj][nk]-=mod;
                    }

                }
            }
        }

        int ans = 0;
        for(int j=0;j<=cnt;++j)
        {
            for(int k=0;k<tot;++k)
            {
                //printf("%d ")
                if(__builtin_popcount(k) >=x)
                {
                    ans+=dp[n][j][k];if(ans>=mod) ans-=mod;
                }
            }
        }

        printf("%d\n",ans);

        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<=cnt;++j)
            {
                for(int k=0;k<tot;++k) dp[i][j][k] = 0;
            }
        }
        for(int i=0;i<=cnt;++i)
        {
            flg[i] = fail[i] = 0;
            for(int c=0;c<26;++c) nxt[i][c] = 0;
        }

    }
    return 0;
}