HDU4821 String-白红宇

HDU4821 String

阅读量：6084 次

发布时间：2019-06-20

本文共 1704 字，大约阅读时间需要 5 分钟。

问题链接：。

字符串有关的算法，大致可以分为三类。一是像本题一样，用哈希函数来解（定长字符串）；二是KMP算法（包括其变种）；三是AC自动机。

这个问题，由于子串之间需要相互比较的组合太多，为了避免重复的比较计算，需要找到一个有效的办法进行处理。不然就组合爆炸了。所以，字符串的哈希函数是一个好的选择。各个子串都计算一个哈希值，字符串比较问题就变成了哈希值比较的问题。进一步，把哈希值放入容器map中，就很快知道各个字串是否都不同（数一下数量）。m*l长的字符串，分为m个l长的子串，各个子串的哈希值作为key放入容器map中，如果容器map中有m个元素，说明各个字串都不相同。

有关字符串哈希值的计算，可以参见：。其中的内容来自百度百科，可惜编码质量太差，不可以直接用的。

计算哈希函数有各种各样的算法。本程序用的是BKDRHash算法，其中的基数一般取素数，以降低哈希值冲突的概率。这个基数，在实际计算时，可以看作是进制。

计算各个字符串的哈希值的方法也是本程序的一个亮点。这里也是按照无名大神的做法做的。

先计算函数hv()，对于字符串s，若其长度为n，则hv(n+1)=0，hv(i)=h(i+1)*base+第i个字符的ASCII值。这里的base为计算哈希值的基数。

再计算函数nbase()，该函数定义为nbase(1)=1，nbase(i)=nbase(i-1)*base。

这样，对于字符串s，第i个字符开始的长度为l的各个子串的哈希值hash(i)＝hv(i)-hv(i+l)*nbase(l)。

以上的哈希值计算方法，主要是为了减少计算量。

同样是为了加快程序运行速度，程序中使用了一个带参数的宏定义“#define getHashval(n, l) hv[n] - hv[n+l] * nbase[l]”，比起使用函数来要好一些，至少省去了程序调用返回和参数传递。这也是有经验程序员的常见做法。

其他需要说明的，都在程序注释里了。

AC程序如下：

/* HDU4821 String */#include 
    
     #include 
     
      #include 
      using namespace std;#define getHashval(n, l) hv[n] - hv[n+l] * nbase[l]typedef unsigned long long ULL;const int base = 131;ULL hv[100000+1];ULL nbase[100000+1];map
       
         hashmap; // 类型为map，实际当作一个集合来使用int main(){    int m, l, count;    string s;    nbase[0] = 1;    for(int i=1; i<=100000; i++)        nbase[i] = nbase[i-1] * base;    // 输入m和l    while (scanf("%d%d", &m, &l) != EOF) {        //输入字符串        cin >> s;        // 计数清零        count = 0;        // 计算长度为l，各个字串的哈希值        int len = (int)s.length();        hv[len] = 0;        for(int i=len-1; i>=0; i--)            hv[i] = hv[i+1] * base + s.at(i);        // 窗口A，长度为m*l，在输入字符串上滑动，每次滑动１个字符，可以看到len-m*l+1个字串        int end = len-m*l;        for(int i=0; i

转载于:https://www.cnblogs.com/tigerisland/p/7564689.html

你可能感兴趣的文章