6 条题解

  • 3
    @ 2023-6-13 15:09:40

    P3808 【模板】AC 自动机（简单版）

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123456;
int n;
struct AC
{
    int tr[MAXN][26], tot; //根节点为 0
    int cnt[MAXN], fail[MAXN];
    void insert(string &s)
    {
        int u = 0;
        // cout << u;
        for (int i = 0; i < s.length(); i++)
        {
            // cout << " -> " << s[i];
            if (!tr[u][s[i] - 'a'])
                tr[u][s[i] - 'a'] = ++tot;
            u = tr[u][s[i] - 'a'];
        }
        cnt[u]++;
        // cout << " cnt:" << cnt[u] << endl;
    }
    queue<int> q;
    void build()
    {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (tr[u][i])
                {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else
                    tr[u][i] = tr[fail[u]][i];
            }
        }
    }
    int query(string &s)
    {
        int res = 0;
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            u = tr[u][s[i] - 'a'];
            for (int j = u; j != 0 && cnt[j] != -1; j = fail[j])
            {
                res += cnt[j];
                cnt[j] = -1;
            }
        }
        return res;
    }
};
AC ac;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        ac.insert(s);
    }
    ac.build();
    cin >> s;
    cout << ac.query(s) << endl;
    return 0;
}
    • 2
      @ 2023-6-13 15:15:32

      P2292 [HNOI2004] L 语言

      #include<bits/stdc++.h>
using namespace std;
const int MAXN = 1123456;
struct AC {
	int tr[MAXN][26], tot; //根节点为 0
	int cnt[MAXN], fail[MAXN],len[MAXN];
	void insert(string &s) {
		int u = 0;
		// cout << u;
		for (int i = 0; i < s.length(); i++) {
			// cout << " -> " << s[i];
			if (!tr[u][s[i] - 'a'])
				tr[u][s[i] - 'a'] = ++tot;
			u = tr[u][s[i] - 'a'];
		}
		cnt[u]++;
		len[u]=s.length();
		// cout << " cnt:" << cnt[u] << endl;
	}
	queue<int> q;
	//当前点有哪些20以内长度的后缀存在 
	int g[MAXN];
	void build() {
		for (int i = 0; i < 26; i++)
			if (tr[0][i])
				q.push(tr[0][i]);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (tr[u][i]) {
					fail[tr[u][i]] = tr[fail[u]][i];
					q.push(tr[u][i]);
				} else
					tr[u][i] = tr[fail[u]][i];
			}
		}
		for(int u=1; u<=tot; u++) {
			g[u]=0;
			for (int i = u; i!=0; i = fail[i])
				if (cnt[i] && len[i] <= 20) g[u] |= (1 << (len[i] - 1));
		}
	}
	bool f[2123456];
	int query(string &s) {
		int res = 0;
		int x = 0; //前 20 位的 f 的状压
		int u = 0;
		f[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			u = tr[u][s[i-1] - 'a'];
			x = ((1 << 20) - 1) & ((x << 1) | f[i - 1]);
			f[i] = (x & g[u]) != 0;
			if(f[i])
				res=max(res,i);
		}
		return res;
	}
};
AC ac;
int n,m;
string s,t;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>s;
		ac.insert(s);
	}
	ac.build();
	for(int i=1; i<=m; i++) {
		cin>>t;
		cout<<ac.query(t)<<"\n";
	}
	return 0;
}
      • 0
        @ 2023-6-13 15:16:29

        P4045 [JSOI2009] 密码

        #include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
int L, n;
struct AC
{
    int tr[MAXN * 10 + 5][26], tot; //根节点为 0
    int fail[MAXN * 10 + 5];
    int ids[MAXN * 10 + 5];
    void insert(string &s, int id)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (!tr[u][s[i] - 'a'])
                tr[u][s[i] - 'a'] = ++tot;
            u = tr[u][s[i] - 'a'];
        }
        ids[u] |= (1 << id);
    }
    queue<int> q;
    void build()
    {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            ids[u] |= ids[fail[u]];
            for (int i = 0; i < 26; i++)
            {
                if (tr[u][i])
                {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                    ids[tr[u][i]] |= ids[fail[tr[u][i]]];
                }
                else
                    tr[u][i] = tr[fail[u]][i];
            }
        }
    }
} ac;
string s[30];
//第i位，匹配到了ac上第j个节点，完成了k这些字符串的方案数
long long f[30][105][(1 << 10) - 1 + 10];
// out
// 寄搜，每个状态能否走到终点。0：没搜过、1：能走到、-1：不能走到
int flag[30][105][(1 << 10) - 1 + 10];
int dfsCheck(int i, int j, int k)
{
    if (flag[i][j][k])
        return flag[i][j][k];
    if (i == L)
    {
        if (k == (1 << n) - 1)
            return flag[i][j][k] = 1;
        else
            return flag[i][j][k] = -1;
    }
    flag[i][j][k] = -1;
    for (int ch = 0; ch < 26; ch++)
    {
        int x = ac.tr[j][ch];
        int y = k | ac.ids[x];
        int res = dfsCheck(i + 1, x, y);
        if (res == 1)
            flag[i][j][k] = 1;
    }
    return flag[i][j][k];
}
char ans[30];
void dfsOut(int i, int j, int k)
{
    if (flag[i][j][k] != 1)
        return;
    if (i == L)
    {
        for (int i = 0; i < L; i++)
            cout << ans[i];
        cout << "\n";
        return;
    }
    for (int ch = 0; ch < 26; ch++)
    {
        int x = ac.tr[j][ch];
        int y = k | ac.ids[x];
        ans[i] = 'a' + ch;
        dfsOut(i + 1, x, y);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> L >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        ac.insert(s[i], i);
    }
    ac.build();
    // dp
    f[0][0][0] = 1;
    for (int i = 0; i < L; i++)
        for (int j = 0; j <= ac.tot; j++)
            for (int k = 0; k <= (1 << n) - 1; k++)
            {
                // f[i][j][k] -> f[i+1][x][y]
                if (f[i][j][k])
                    for (int ch = 0; ch < 26; ch++)
                    {
                        int x = ac.tr[j][ch];  //下一个字符选 ch 对应的下一个节点
                        int y = k | ac.ids[x]; //下一个节点包括当前节点经过了哪些单词
                        f[i + 1][x][y] += f[i][j][k];
                    }
            }
    long long ans = 0;
    for (int i = 0; i <= ac.tot; i++)
        ans += f[L][i][(1 << n) - 1];
    // out
    if (ans > 42)
        cout << ans << "\n";
    else
    {
        cout << ans << "\n";
        dfsCheck(0, 0, 0);
        dfsOut(0, 0, 0);
    }
    return 0;
}
        • 0
          @ 2023-6-13 15:15:59

          P2414 [NOI2011] 阿狸的打字机

          #include<bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
struct AC {
	int tr[MAXN][26], tot;//根节点为 0
	int idx[MAXN],idTot;//第i个字符串对应的位置
	int fa[MAXN], fail[MAXN];
	vector<int> FT[MAXN];//fail tree
	int dfn[MAXN],dfnn[MAXN],dfId;//dfs序(in,out)
	void dfs(int u) { 
		dfn[u]=++dfId;
		for(int i=0; i<FT[u].size(); i++) {
			int v=FT[u][i];
			dfs(v);
		}
		dfnn[u]=dfId;
	}
	void insert(string &s) {
		int u = 0;
		for (int i = 0; i < s.length(); i++) {
			if('a'<=s[i]&&s[i]<='z') {
				if (!tr[u][s[i] - 'a'])
					tr[u][s[i] - 'a'] = ++tot;
				int nxt=tr[u][s[i] - 'a'];
				fa[nxt]=u;
				u = nxt;
			} else if(s[i]=='P') {
				idx[++idTot] = u;
			} else if(s[i]=='B') {
				u=fa[u];
			}
		}
	}
	queue<int> q;
	void build() {
		for (int i = 0; i < 26; i++)
			if (tr[0][i])
				q.push(tr[0][i]);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (tr[u][i]) {
					fail[tr[u][i]] = tr[fail[u]][i];
					q.push(tr[u][i]);
				} else
					tr[u][i] = tr[fail[u]][i];
			}
		}
		//build fail tree
		for(int i=1; i<=tot; i++){
			FT[fail[i]].push_back(i);
		}
		dfs(0);
	}
};
AC ac;
string s;
int n,m;
//离线询问
vector<pair<int,int> > qa[112345];
int ans[112345];
//树状数组
int ta[MAXN];
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int y) {
	for(int i=x; i<=n; i+=lowbit(i))
		ta[i]+=y;
}
int sum(int x) {
	int res=0;
	for(int i=x; i>=1; i-=lowbit(i))
		res+=ta[i];
	return res;
}
int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	cin>>s;
	n=s.length();
	ac.insert(s); 
	ac.build();
	cin>>m;
	for(int i=1; i<=m; i++) {
		int xx,yy;
		cin>>xx>>yy;
		qa[yy].push_back(make_pair(xx,i));
	}
	int u=0;
	int nowQ=0;
	for(int i=0; i<s.length(); i++) {
		if('a'<=s[i]&&s[i]<='z') {
			u=ac.tr[u][s[i]-'a'];
			add(ac.dfn[u],1);
		} else if(s[i]=='B') {
			add(ac.dfn[u],-1);
			u=ac.fa[u];
		} else if(s[i]=='P') {
			nowQ++;
			for(int j=0; j<qa[nowQ].size(); j++) {
				int x=qa[nowQ][j].first;
				int id=qa[nowQ][j].second;
				ans[id]=sum(ac.dfnn[ac.idx[x]])-sum(ac.dfn[ac.idx[x]]-1);
			}
		}
	}
	for(int i=1; i<=m; i++)
		cout<<ans[i]<<"\n";
	return 0;
}
          • 0
            @ 2023-6-13 15:12:15

            P5357 【模板】AC 自动机（二次加强版）

            #include <bits/stdc++.h>
using namespace std;
const int MAXN = 212345;
int n;
struct AC
{
    int tr[MAXN][26], tot; // 根节点为 0
    int cnt[MAXN], fail[MAXN];
    int idx[MAXN]; // 每个模式串对应的终点坐标
    // fail树相关
    int inD[MAXN];
    void insert(string &s, int id)
    {
        int u = 0;
        // cout << u;
        for (int i = 0; i < s.length(); i++)
        {
            // cout << " -> " << s[i];
            if (!tr[u][s[i] - 'a'])
                tr[u][s[i] - 'a'] = ++tot;
            u = tr[u][s[i] - 'a'];
        }
        idx[id] = u;
        // cnt[u]++;
        // cout << " cnt:" << cnt[u] << endl;
    }
    queue<int> q;
    void build()
    {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (tr[u][i])
                {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    inD[tr[fail[u]][i]]++;
                    q.push(tr[u][i]);
                }
                else
                    tr[u][i] = tr[fail[u]][i];
            }
        }
    }
    bool vis[MAXN];
    void query(string &s)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            u = tr[u][s[i] - 'a'];
            cnt[u]++;
        }
        queue<int> q;
        for (int i = 0; i <= tot; i++)
            if (inD[i] == 0)
                q.push(i), vis[i] = true;
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
            int nxt = fail[now];
            inD[nxt]--;
            cnt[nxt] += cnt[now];
            if (inD[nxt] == 0 && !vis[nxt])
                q.push(nxt), vis[nxt] = true;
        }
    }
};
AC ac;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        ac.insert(s, i);
    }
    ac.build();
    cin >> s;
    ac.query(s);
    /*
    for (int i = 0; i <= ac.tot; i++)
    {
        cout << i << ": ";
        for (int j = 0; j <= 1; j++)
            cout << ac.tr[i][j] << " ";
        cout << ", " << ac.fail[i] << "\n";
    }
    */
    for (int i = 1; i <= n; i++)
        cout << ac.cnt[ac.idx[i]] << "\n"; //<< " " << ac.idx[i]
    return 0;
}
            • 0
              @ 2023-6-13 15:11:27

              P3796 【模板】AC 自动机（加强版）

              #include <bits/stdc++.h>
using namespace std;
const int MAXT = 50 + 5;
const int MAXN = 150 + 5;
int T, n;
string s[MAXT][MAXN], t;
int scnt[MAXT][MAXN];
struct AC
{
    int tr[MAXN * 70 + 5][26], tot; //根节点为 0
    int cnt[MAXN * 70 + 5], fail[MAXN * 70 + 5], idx[MAXN * 70 + 5];
    void insert(string &s, int id)
    {
        int u = 0;
        // cout << u;
        for (int i = 0; i < s.length(); i++)
        {
            // cout << " -> " << s[i];
            if (!tr[u][s[i] - 'a'])
                tr[u][s[i] - 'a'] = ++tot;
            u = tr[u][s[i] - 'a'];
        }
        idx[u] = id;
        // cout << " cnt:" << cnt[u] << endl;
    }
    queue<int> q;
    void build()
    {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (tr[u][i])
                {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else
                    tr[u][i] = tr[fail[u]][i];
            }
        }
    }
    int query(string &s)
    {
        int res = 0;
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            u = tr[u][s[i] - 'a'];
            for (int j = u; j != 0 && cnt[j] != -1; j = fail[j])
                cnt[j]++;
        }
        for (int i = 0; i <= tot; i++)
            if (idx[i])
                res = max(res, cnt[i]), scnt[T][idx[i]] = cnt[i];
        return res;
    }
};
AC ac[MAXT];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n)
    {
        if (n == 0)
            break;
        T++;
        for (int i = 1; i <= n; i++)
        {
            cin >> s[T][i];
            ac[T].insert(s[T][i], i);
        }
        ac[T].build();
        cin >> t;
        int ans = ac[T].query(t);
        cout << ans << "\n";
        for (int i = 1; i <= n; i++)
            if (scnt[T][i] == ans)
                cout << s[T][i] << "\n";
    }
    return 0;
}
              • 1

              扩展题单 - AC自动机

              信息

              ID
              1287
              时间
              1000ms
              内存
              256MiB
              难度
              6
              标签
              递交数
              17
              已通过
              11
              上传者
              1. 评测队列
              2. 服务状态
              3. 兼容模式
              4. 主题
              2. 陕ICP备2022006801号-1
              3. Worker 0, 10ms
              4. Powered by Hydro v4.14.1 Community, Modified by 33DAI