首页 > 其他 > 详细

HDU 7064 - Singing Superstar

时间:2021-08-12 23:15:22      阅读:59      评论:0      收藏:0      [点我收藏+]

https://acm.hdu.edu.cn/showproblem.php?pid=7064

  • 注意开数组的大小
  • 注意优化(插入的时候判断长度是否可行)
const int maxn = 1e5 + 7;

int n, t, m, stp = 30;
int nex[maxn * 33][27], cnt;
vector<int> vec[maxn * 40];

void insert(char *s) {
    int l = strlen(s);
    for (int i = 0; i < l; i++) {
        int p = 0;
        for (int j = i; j < i + stp && j < l; j++) {
            int c = s[j] - ‘a‘;
            if (!nex[p][c])
                nex[p][c] = ++cnt;
            p = nex[p][c];
            if (vec[p].size() == 0 || j - vec[p].back() >= j - i + 1)
                vec[p].push_back(j);
        }
    }
}

int find(char *s) {
    int l = strlen(s), p = 0;
    for (int i = 0; i < l; i++) {
        int c = s[i] - ‘a‘;
        if (!nex[p][c])
            nex[p][c] = ++cnt;
        p = nex[p][c];
    }
    return vec[p].size();
}

char s[maxn];
char pt[maxn];

void solve() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);
        insert(s);
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%s", pt);
            int x = find(pt);
            printf("%d\n", x);
        }
        for (int i = 0; i <= cnt; i++) {
            vec[i].clear();
            for (int j = 0; j <= 26; j++)
                nex[i][j] = 0;
        }
        cnt = 0;
    }

HDU 7064 - Singing Superstar

原文:https://www.cnblogs.com/maymi/p/15134808.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!