时间戳

首页 > 技术文章 > 1691：文章评分

1691：文章评分

lyc-lb-blogs 2021-08-11 21:21 原文

1691：文章评分


时间限制: 1000 ms         内存限制: 262144 KB
提交数: 1094     通过数: 175

【题目描述】

nodgd的文章由$n$个小写英文字母组成。文章的一个子串指的是文章中的一段连续的字母，子串的长度就是这一段的字母个数。nodgd在文章中用了排比、对偶、前后照应之类的手法，所以就有很多个子串是相同或者相近的。为了向大家证明这是一篇好文章，nodgd决定给自己的文章进行评分。nodgd 首先确定了一个整数$m$，然后统计出文章中有多少个不相同的长度为$m$的子串，这个数量就是文章的评分。

【输入】

第一行包含两个整数$n,m$，表示文章的长度和需要统计的子串长度。

第二行包含一个长度为$n$的只包含小写字母的字符串。

【输出】

一行一个整数，表示文章的评分。

【输入样例】

5 3 
aaaab

【输出样例】

2

【提示】

【样例解释1】

长度为$3$的子串有$3$个，分别是 $aaa,aaa,aab$，其中不同的只有$2$个。

【输入样例2】

9 3 
abcabacba

【输出样例2】

7

【样例解释2】

共有$7$个长度为$3$的子串，每个长度为$3$的子串都不同。

【数据规模】

对于 30%的数据，$1≤m≤n≤200$。

对于 50%的数据，$1≤m≤n≤2000$。

对于另外 20%的数据，$1≤m≤50≤n≤200000$。

对于 100%的数据，$1≤m≤n≤200000$。

从头到扫一遍， 计算长度为m的子串的Hash值，用Hash表判重即可

注意单哈希可能会重复，要用双哈希，不建议使用ull自溢出

#include <bits/stdc++.h>

using namespace std;

const int p = 1e9 + 7, q = 1e9 + 9;

map <int, bool> m1 ,m2;

const int N = 2e5 + 10;
char s[N];
long long p1[N],p2[N];
int n, m;
long long sum1[N],sum2[N];

int query1(int l,int r)
{
    return ((sum1[r] - sum1[l - 1] * p1[r - l + 1] % p) % p + p) % p;
}

int query2(int l,int r)
{
    return ((sum2[r] - sum2[l - 1] * p2[r - l + 1] % q) % q + q) % q;
}

int main()
{
    scanf("%d %d", &n, &m);
    scanf("%s",s + 1); 
    p1[0] = p2[0] = 1;

    for(int i = 1; i <= n; i++)
    {
        sum1[i] = ((sum1[i - 1] * 2711 % p) + s[i] - 'a' + 1 ) % p;
        sum2[i] = ((sum2[i - 1] * 3769 % q) + s[i] - 'a' + 1 ) % q;

        p1[i] = p1[i - 1] * 2711 % p;
        p2[i] = p2[i - 1] * 3769 % q;
		/*随便取两个p, q，不建议用比较小的17, 19之类的*/

    }
    long long ans = 0 ;
    for(int i = 1; i + m - 1 <= n; i++)
    {
        int Hash1 = query1(i, i + m - 1);
        int Hash2 = query2(i, i + m - 1);

        if(!m1[Hash1] || !m2[Hash2])
        {
            m1[Hash1] = m2[Hash2] = 1;
            ans++;
        }

    }

    printf("%lld", ans);
    return 0;
}

推荐阅读