社区讨论

关于gets()

题目总版参与者 9已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@locp3di4
此快照首次捕获于
2023/10/30 17:26
2 年前
此快照最后确认于
2023/11/05 04:19
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int trie[200010][26], fail[200010], res[200010], id[200010], que[200010], tot, len, n, a, b(1);
char s[2000010];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s + 1; //->gets(s + 1);
        len = strlen(s + 1);
        for (int j = 1; j <= len; ++j) {
            int ch = s[j] - 'a';
            if (!trie[id[i]][ch]) trie[id[i]][ch] = ++tot;
            id[i] = trie[id[i]][ch];
            //cout<<"id["<<i<<"] = "<<id[i]<<endl;
        }
    }
    for (int i = 0; i < 26; ++i) if (trie[0][i]) que[++a] = trie[0][i];
    while (b <= a) {
        int u = que[b++];
        for (int i = 0; i < 26; ++i) {
            if (trie[u][i]) {
                fail[trie[u][i]] = trie[fail[u]][i];
                que[++a] = trie[u][i];
            } else trie[u][i] = trie[fail[u]][i];
        }
    }
    cin >> s + 1; //->gets(s + 1);
    
	len = strlen(s + 1);
    //printf("%s %d\n",s+1,len);
    for (int i = 1, p = 0; i <= len; ++i) {
        int ch = s[i] - 'a';
        p = trie[p][ch];
        res[p]++;
    }
    for (int i = tot; i >= 1; --i) res[fail[que[i]]] += res[que[i]];
    for (int i = 1; i <= n; ++i) cout << res[id[i]] << "\n";
}

回复

11 条回复,欢迎继续交流。

正在加载回复...