http://acm.scau.edu.cn:8000/uoj/mainMenu.html

18000 Two String

时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题语言: 不限定

Description

Given two string A and B and three kinds of operations as following:

(1)Push_back c            add a character c at the back of string B

(2)Push_front c           add a character c in front of string B

(3)Query                  calculate and output how many times B appears in A

could you calculate and output the right answer for each query?

输入格式

The first line contains the string A ,the second line contains the string B ,the third line contains an integer M (1 <= M <= 2000),
 expressing the number of operation, Each of the following M lines contains one of the above-mentioned three operations.

total length of the string does not exceed 5000,all character in the input are the lower case Latin alphabet

输出格式

For each query, output a line containing the answer.

输入样例

abcabc

a

5

Query

Push_back b

Query

Push_front a

Query

aaaaa

a

5

Query

Push_back a

Query

Push_front a

Query

输出样例

来源

星尘

作者

admin

一定要注意到的是，

total length of the string does not exceed 5000,

就是所有样例的字符全加起来不会超过5000，其实我觉得这样给数据范围很坑爹。不如一个样例一个样例给我。

一直不敢做，其实就是暴力。

对于每种push，暴力进行。

每种查询，kmp一次。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  + ;

char str[maxn];

char sub[][maxn];

int lensub;

int lenstr;

int now;

int tonext[maxn];

void get_next(int now) {

    int i = , j = ;

    tonext[] = ;

    while (i <= lensub) {

        if (j ==  || sub[now][i] == sub[now][j]) {

            tonext[++i] = ++j;

        } else j = tonext[j];

    }

}

int kmp(int now) {

    get_next(now);

    int i = , j = ;

    int ans = ;

    while (i <= lenstr) {

        if (j ==  || str[i] == sub[now][j]) {

            ++i;

            ++j;

        } else j = tonext[j];

        if (j == lensub + ) {

            ans++;

            j = tonext[j];

        }

    }

    return ans;

}

void work() {

    lenstr = strlen(str + );

    lensub = strlen(sub[now] + );

    int q;

    scanf("%d", &q);

    char t[];

    for (int i = ; i <= q; ++i) {

        scanf("%s", t + );

        if (t[] == 'Q') {

            printf("%d\n", kmp(now));

        } else {

            char tt[];

            scanf("%s", tt);

            if (strcmp("Push_back", t + ) == ) {

                sub[now][++lensub] = tt[];

            } else {

                for (int i = ; i <= lensub; ++i) {

                    sub[!now][i + ] = sub[now][i];

                }

                sub[!now][] = tt[];

                now = !now;

                lensub += ;

            }

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    while (scanf("%s%s", str + , sub[now] + ) != EOF) work();

    return ;

}

巴特西

18000 Two String 暴力。——— 读题