【链接】h在这里写链接

【题意】

让你维护字符串的一段区间内T子串的个数。

【题解】

因为t不大,所以。

暴力维护一下a[i]就好。

a[i]表示的是S串从i位置开始,能和T串匹配几个字符。

用树状数组维护区间内a[i]==lent的个数就好。

修改,还是暴力改就行。只会影响到那几个位置的。

【错的次数】

【反思】

匹配的部分写在一个函数里面比较好,用起来比较方便。

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

struct BI {

    int a[N + 10];

    int lowbit(int x) {

        return x&(-x);

    }

    void add(int x, int y) {

        while (x <= N) {

            a[x] += y;

            x += lowbit(x);

        }

    }

    int sum(int x) {

        int now = 0;

        while (x > 0) {

            now += a[x];

            x -= lowbit(x);

        }

        return now;

    }

    int get_sum(int l, int r) {

        return sum(r) - sum(l - 1);

    }

}BIT;

char s[N + 20], t[20 + 20];

int Q,a[N+20],lens,lent;

void pipei(int pos) {

    a[pos] = 0;

    for (int j = 1; j <= lent && pos + j - 1 <= lens; j++)

        if (s[pos + j - 1] == t[j])

            a[pos] = j;

        else

            break;

}

void geta() {

    for (int i = 1; i <= lens; i++) {

        pipei(i);

        if (a[i] == lent) BIT.add(i, 1);

    }

}

void in() {

    scanf("%d", &Q);

    scanf("%s%s", s + 1, t + 1);

    lens = strlen(s + 1), lent = strlen(t + 1);

}

void cl() {

    for (int i = 1; i <= Q; i++) {

        char r[5];

        scanf("%s", r);

        if (r[0] == 'Q') {

            int a, b;

            scanf("%d%d", &a, &b);

            if (b - lent + 1 < a)

                puts("0");

            else

                printf("%d\n", BIT.get_sum(a,b-lent+1));

        }

        else {

            int pos;

            scanf("%d%s", &pos, r);

            s[pos] = r[0];

            for (int j = max(1,pos - lent + 1); j <= pos; j++) {

                int temp = a[j];

                pipei(j);

                if (temp == lent) {

                    if (a[j] != lent) {

                        BIT.add(j, -1);

                    }

                }

                else

                    if (a[j] == lent)

                        BIT.add(j, 1);

            }

        }

        puts("");

    }

}

int main() {

    //freopen("F:\\rush.txt", "r", stdin);

    //ios::sync_with_stdio(0), cin.tie(0);

    int T;

    scanf("%d", &T);

    while (T--) {

        in();

        geta();

        cl();

    }

    return 0;

}

巴特西

【2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛 G】Query on a string

【链接】h在这里写链接

【题意】

【题解】

【错的次数】

【反思】

【代码】

最新文章

热门文章