acwing::acwing3412类 参考

AcWing 4312. 出现次数 更多...

#include <acwing.h>

静态 Public 成员函数
static int	main (istream &cin, ostream &cout)

详细描述

AcWing 4312. 出现次数

在文件 acwing.h 第 1751 行定义.

成员函数说明

main()

int acwing::acwing3412::main ( istream &  cin, ostream &  cout  )

static

在文件 acwing.cpp 第 5309 行定义.

                                                    {
        int n;
        int m;
        int q;
        cin >> n >> m >> q;
        if(m > n) {
            for(int i = 0; i < q; i++) {
                cout << 0 << endl;
            }
            return 0;
        }
        string s;
        string t;
        cin >> s >> t;
        set<int> sub_end;
        set<int> sub_start;
        int sub_count = 0;
        for(int i = 0; i + m <= n; i++) {
            string str = s.substr(i, m);
            if(str == t) {
                sub_count++;
                sub_start.insert(i);
                sub_end.insert(i + m - 1);
            }
        }
        vector sub_end_count(n + 1, 0);
        vector sub_start_count(n + 1, 0);
        int current = 0;
        for(int i = 0; i < n + 1; i++) {
            if(sub_end.contains(i)) {
                current++;
            }
            sub_end_count[i] = current;
        }
        current = 0;
        for(int i = n; i >= 0; i--) {
            if(sub_start.contains(i)) {
                current++;
            }
            sub_start_count[i] = current;
        }
        for(int i = 0; i < q; i++) {
            int l;
            int r;
            cin >> l >> r;
            int ans = sub_end_count[r - 1] - (sub_count - sub_start_count[l - 1]);
            cout << max(ans, 0) << endl;
        }
        return 0;
    }

被这些函数引用 acwing::TEST().

---

该类的文档由以下文件生成:

• acwing.h
• acwing.cpp