首页 > 编程语言 > 详细

Acwing-----算法基础课之第二讲

时间:2020-04-05 17:46:28      阅读:720      评论:0      收藏:0      [点我收藏+]

831. KMP字符串

#include <iostream>

using namespace std;
const int N = 10010, M = 100010;

int n, m;
char s[M], p[N];
int ne[N];

int main() {
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; ++i) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) ++j;
        ne[i] = j;
    }
    
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) ++j;
        if (j == n) {
            cout << i - n << " ";
            j = ne[j];
        }
    }
    return 0;
}

835. Trie字符串统计

#include <iostream>
using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx, n;
char str[N];

void insert(char* str) {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - ‘a‘;
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char* str) {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - ‘a‘;
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}


int main() {
    cin >> n;
    while (n--) {
        char op[2];
        scanf("%s%s", &op, &str);
        if (*op == ‘I‘) insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}

Acwing-----算法基础课之第二讲

原文:https://www.cnblogs.com/clown9804/p/12637913.html

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