题目描述

没有用map，简单写的双指针，复杂度$O(n*T)$, n为字母串长度，T为8字符小串数，但只过了6/10个测试点，应该是常数过大了

样例

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
char str[N];
int let[N][30];
int letnow[N];
long long result;
int T;

void add(int e)
{
    char le[10];
    cin >> le;
    for(int i = 0; i < 8; i ++)
        let[e][le[i]-'a'] ++;
}

void check()
{
    for(int i = 1; i <= T; i ++)
    {
        bool fit = true;
        for(int j = 0; j <= 25; j ++)
            if(let[i][j]!=letnow[j])
            {
                fit = false;
                break;
            }
        if(fit) result ++;
    }
}

int main()
{
    cin >> str;
    cin >> T;
    for(int i = 1; i <= T; i ++) add(i);
    for(int i = 0; i < 8; i ++) letnow[str[i]-'a'] ++;
    check();
    int i = 8;
    while(str[i])
    {
        letnow[str[i]-'a']++;
        letnow[str[i-8]-'a']--;
        check();
        i++;
    }
    cout << result << endl;
    return 0;
}