题意

给出一个数组 s 串，和数组 t 串，那么如果两者长度相同且两者所含的数字全部相同，则说这两个串相似。

给定原始串 S ，以及 m 个询问 T 串，问 S 串有多少个连续子串和 T 串相似。

分析

2017年计蒜之道第五场的题目。题目很有趣，虽然比赛里只水出了中等难度。看了题解，学到了新姿势！

这道题，为了优化复杂度，就是要快速判断两个数组是否完全相同，

对于中等难度，询问的次数很少，那么我们就要加快 T 和 S 的子串的比较速度，那么可以把 1到50000 (n <= 50000)分别映射到64位无符号整型数（允许自然溢出），对于查询的串，把对应的映射后的值加起来，和 S 的子串（也是映射后的）分别比较即可。复杂度 \(O(nm)\) 。

对于困难难度，询问次数1e5，但是注意到题目给出的查询的串 T 的总长度 (len) <= 2e5 ，那么最多只有 \(\sqrt{len}\) 种长度，对于每一种长度，求出 S 的所有子串，并把这些子串和查询的串全部放到一个数组里面排序，通过遍历一遍数组即可算出答案。复杂度\(O(nlogn\sqrt{len})\) 。

我把困难难度的代码再交到中等难度题目里面，发现运行时间893ms，而 \(O(nm)\) 的算法只需要66ms，因为困难难度的代码的复杂度已经和查询的次数无关了，对于不同数据，设计不同的算法，要充分利用题目给出的信息。

code （\(O(nm)\)）

#include
    
     using namespace std;typedef long long ll;const int MAXN = 5e4 + 10;int n, m;int a[MAXN];int t[MAXN];unsigned long long Z[MAXN];int main() {    srand(timezone);    for(int i = 0; i < MAXN; i++) {        Z[i] = (unsigned long long)rand() * rand() * rand() * rand();    }    cin >> n;    for(int i = 0; i < n; i++) {        cin >> a[i];    }    cin >> m;    while(m--) {        int k, num = 0;        cin >> k;        if(k > n) {            puts("0");            continue;        }        int cnt = 0;        unsigned long long A = 1, T = 1;        for(int i = 0; i < k; i++) {            cin >> t[i];            T += Z[t[i]];            A += Z[a[i]];        }        if(A == T) {            cnt++;        }        for(int i = k; i < n; i++) {            A -= Z[a[i - k]];            A += Z[a[i]];            if(A == T) cnt++;        }        cout << cnt << endl;    }    return 0;}
    

code （\(O(nlogn\sqrt{len})\)）

#include
    
     using namespace std;typedef unsigned long long ull;const int MAXN = 1e5 + 10;int n, m;int s[MAXN];ull Z[MAXN];struct A {    int id, k;    ull num;    bool operator<(const A&other) {        return k < other.k;    }} a[MAXN];struct node {    int q, id;    ull num;    node() {}    node(int q_, int id_, ull num_): q(q_), id(id_), num(num_) {}    bool operator<(const node&other) {        if(num != other.num) return num < other.num;        return q > other.q;    }} d[MAXN * 2];int ans[MAXN * 2];int main() {    srand(timezone);    for(int i = 0; i < MAXN; i++) {        Z[i] = (ull)rand() * rand() * rand() * rand();    }    cin >> n;    for(int i = 0; i < n; i++) {        cin >> s[i];    }    cin >> m;    for(int i = 0; i < m; i++) {        cin >> a[i].k;        a[i].id = i;        for(int j = 0; j < a[i].k; j++) {            int p;            cin >> p;            a[i].num += Z[p];        }    }    sort(a, a + m);    int l = 0, r = 0;    while(r < m) {        int cnt = 0;        d[cnt++] = node(1, a[r].id, a[r].num);        while(r < m && a[r + 1].k == a[r].k) {            r++;            d[cnt++] = node(1, a[r].id, a[r].num);        }        int k = a[r].k;        if(k > n) {            ans[a[l].id] = 0;            continue;        }        ull sum = 0;        for(int i = 0; i < k; i++) {            sum += Z[s[i]];        }        if(k) d[cnt++] = node(0, 0, sum);        for(int i = k; i < n; i++) {            sum -= Z[s[i - k]];            sum += Z[s[i]];            d[cnt++] = node(0, 0, sum);        }        sort(d, d + cnt);        int l1 = 0, r1 = 0, l2 = 0, r2 = 0;        while(l1 < cnt) {            int flg = 0;            for(int i = l1; i < cnt; i++) {                if(d[i].q) {                    l1 = i;                    flg = 1;                    break;                }            }            if(!flg) break;            r1 = l1;            while(r1 < cnt && d[r1 + 1].q && d[r1 + 1].num == d[r1].num) r1++;            int l2 = r1 + 1, r2 = l2;            if(l2 < cnt && !d[l2].q && d[l2].num == d[r1].num) {                while(r2 < cnt && !d[r2 + 1].q && d[r2 + 1].num == d[r2].num) r2++;                for(int i = l1; i <= r1; i++) {                    ans[d[i].id] = r2 - l2 + 1;                }                l1 = r2 + 1;            } else l1 = r2;        }        r++;    }    for(int i = 0; i < m; i++) {        cout << ans[i] << endl;    }    return 0;}