HDU 2222

Type: AC自动机

题意

给你几个子串,再给你一个主串,问你有多少个子串在主串中出现过.

输入

T,N,接下来N行输入N个字符串,最后一行输入一个主串.

输出

一个整数,有多少子串可以在主串中被匹配到

题解

注意,每个子串可能是相同的,所以我们不能在尾节点记录子串的下标,而应该记录子串的个数.最后加进去即可

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)500005;
const int max_tot=(int)1e6+6;

int T,N;
char str[10010][60],tot[max_tot];

struct AC_AutoMaton{
    static const int sigma_size=26;
    static const char first_caractar='a';
    int ch[maxn][sigma_size];
    int f[maxn],last[maxn];
    int cnt[maxn],val[maxn];
    int siz;

    int ans;

    void init(){
        siz=ans=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }

    int ord(char c){
        return c-first_caractar;
    }

    void insert(char *s){
        int u=0,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=++siz;
            u=ch[u][c];
       }
       ///表示以第u棵节点为字符串最后一个字符节点的个数
       ///如果想存储该节点代表的是哪个字符串.即存储该字符串的下标
       ///val[u]=v;(v是下标)
       ///但是这样存储就会出现无法统计之前有多少个重复字符串
       ///比如这道题如果输入
       ///3
       ///sha
       ///sha
       ///sha
       ///shashasha
       ///则用第一种方法最后结果是3
       ///但用第二种方法只能匹配一次sha
       val[u]++;
    }
    //Fail树
    void getFail(){
        queue<int> Q;
        f[0]=0;
        ///遍历取出第一个节点所有的前向字符
        for(int c=0;c<sigma_size;++c){
            int u=ch[0][c];
            if(u){
                f[u]=last[u]=0;
                Q.push(u);
            }
        }
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                int u=ch[k][c];
                if(!u) continue;
                Q.push(u);
                int v=f[k];
                while(v && !ch[v][c]) v=f[v];
                f[u]=ch[v][c];
                last[u]=val[f[u]]?f[u]:last[f[u]];
            }
        }
    }

    ///统计
    void add(int u){
        if(u){
            if(!cnt[u]) ans+=val[u],cnt[u]=1;
            add(last[u]);
        }
    }

    ///多模式匹配
    void Find(char *s){
        int u=0,n=strlen(s);
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            if(val[u]) add(u);
            else if(last[u]) add(last[u]);
        }
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i]);
        }
        aho.getFail();
        scanf("%s",tot);
        aho.Find(tot);
        printf("%d\n",aho.ans);
    }
    return 0;
}

Wannafly 挑战赛11

A. 水

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n;
    cin>>n;
    cout<<n+1<<endl;
    return 0;
}

B: 组合数学, 预处理阶乘逆元

因为不可能暴力,所以我们想到是推式子
我们可以把前几项放在Excel表中推一下
然后我们会发现 关于m,n的式子为

常数k*b^(m-1)*a^(n-m)

该式子即为目标结果

如何求常数k呢

设k[n][m] 为n行m列的常数

我们发现 k[n][m]=k[n-1][m]+k[n-1][m-1]
这个式子和组合数学里的 C(n,k)+C(n,k+1)=C(n+1,k+1) 相似

所以 k[n][m]=C(n-1,m-1)

但因为我们无法以O(N^2)解决这道题,所以不能用递推式求组合数

那我们就直接用 组合数的公式求

C(n,m)=n!/((n-m)!*m!)

预处理n!和n!的逆元

这里因为数组有限,无法使用递推式求逆元,

所以我们用费马小定理求逆元

a^(p-1)≡1(mod p)

则 a^(p-2) 即为 a 对于 p 的逆元.

预处理即可

当n < m时,ans=0

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int maxn = 100000;

int a,b,n,m;
int T;

ll inv[maxn+10],fac[maxn+10];
///预处理N!的逆元
//费马小定理
/*
 *假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
 *根据这个性质我们可以知道 a的逆元为a^(p-2)
 */
ll fast_pow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1ll)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1ll;
    }
    return ans;
}
void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=maxn;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=fast_pow(fac[i],MOD-2ll);
    }
}
ll C(ll a,ll b)
{
    return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}

int main(){
    pre();
    scanf("%d",&T);
    for(int k=0;k<T;++k){
        scanf("%d%d%d%d",&a,&b,&n,&m);
        if(n<m){
            printf("0\n");
            continue;
        }
        int t=n-1,s=m-1;
        ll ans=1;

        ans=ans*C(n-1,m-1)%MOD*fast_pow(a,n-m)%MOD*fast_pow(b,m-1)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}


/// C(N-1,M-1)*b^(M-1)*a^(N-M)
/// N<M 0