`
暴风雪
  • 浏览: 389096 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[字符串hash]poj 1200:Crazy Search

阅读更多

大致题意:
    给出两个数n,nc,并给出一个由nc种字符组成的字符串。求这个字符串中长度为n的子串有多少种。

 

大致思路:
    裸哈希之,将长度为n的子串看作 n位的 nc进制数,将问题转化为共有多少种数字。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int hash[30];
bool loc[20000000];
char str[1000000];
int main(){
    int n,m,cnt,sum,len,ans,i,j;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(loc,0,sizeof(loc));
        memset(hash,0,sizeof(hash));
        scanf("%s",str);
        len=strlen(str);
        cnt=1;
        ans=0;
        for(i=0;i+n<=len;i++){
            sum=0;
            for(j=i;j<i+n;j++){
                if(!hash[str[j]-'a']){
                    hash[str[j]-'a']=cnt++;
                }
                sum*=m;
                sum+=hash[str[j]-'a'];
            }
            if(!loc[sum]){
                loc[sum]=1;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
 

 

0
0
分享到:
评论

相关推荐

    经典 的POJ 分类

    - POJ 3349、POJ 3274:字符串匹配及Hash应用。 - POJ 2151、POJ 1840:利用Hash进行快速查询。 - POJ 2002、POJ 2503:Hash表在实际问题中的运用。 ### 搜索算法 #### 深度优先搜索 (DFS) - **题目示例**: -...

    hash字符串函数总结

    本文将对几种常见的字符串哈希函数进行总结。 1. **SDBM Hash Function**: SDBM Hash(Simple Database Manipulation)是由Peter J. Weinberger设计的一种快速哈希函数。它的核心思想是每次迭代时将当前字符与上...

    ACM-字符串处理专练

    2. **字符串搜索**:包括线性搜索和更高效的算法,如KMP(Knuth-Morris-Pratt)算法,Boyer-Moore算法,以及Rabin-Karp rolling hash。这些算法用于在一个字符串中查找子串,且在某些情况下可以实现快速定位。 3. *...

    自己实现的字符串hash类

    在编程领域,哈希表(Hash Table)是一种高效的数据结构,它通过计算字符串的哈希值来实现快速的查找、插入和删除操作。哈希表通常由数组和哈希函数组成,其中哈希函数将键(Key)映射到数组的特定位置。在这个场景...

    各种字符串Hash函数比较[借鉴].pdf

    【字符串Hash函数】是计算机科学中用于快速查找和存储字符串的一种高效算法。它将字符串转换为一个固定长度的数值(通常称为哈希值),这个数值可以作为字符串的唯一标识。在对比不同字符串Hash函数时,主要关注以下...

    字符串hash以及7大问题

    字符串hash以及7大问题,有兴趣的同学可以看一下。。。。

    获取一个字符串的散列hash

    在给定的标题和描述中,“获取一个字符串的散列hash”指的是利用特定算法将一个字符串转换为其对应的散列值。这个过程对于JavaScript开发者来说尤其有用,因为可以用于创建唯一标识符、验证数据完整性或加密敏感信息...

    暴雪字符串哈希.txt

    功能:计算字符串的哈希值 参数:lpszString:字符串的地址 dwHashType:哈希值类型 dwHashType = 0时计算的哈希值用于确定字符串在哈希表中的位置; dwHashType = 1,dwHashType = 2时计算的哈希值用于验证字符...

    字符串hash的研究

    当我们阅读《关于Hash的研究.doc》这篇文档时,可能会了解到更多关于字符串hash的优化技巧和实践经验,例如使用开放寻址法或链地址法处理哈希冲突,以及如何根据具体场景选择合适的哈希函数。此外,文档可能还会涉及...

    数据结构(字符串匹配,hash,二叉树)训练

    这是一个查找一个字符串(模式串)在另一个字符串(目标串)中出现位置的问题。传统的朴素字符串匹配算法时间复杂度较高,而哈希函数的引入可以显著提高效率。哈希函数将字符串转化为固定大小的数值,使得比较变得...

    字符串hash算法比较

    字符串哈希算法是一种将任意长度的字符串映射到固定长度哈希值的算法,通常用于快速查找、数据索引和内存管理等。在计算机科学中,哈希函数的设计至关重要,因为它直接影响到哈希表的性能。本文将探讨几种经典的字符...

    经典字符串hash函数

    在计算机科学中,字符串哈希(Hash)函数是一种将任意长度的字符串映射为固定长度数值的方法,这个数值通常称为哈希值。哈希函数在数据结构、算法和信息安全等领域有着广泛的应用,如散列表的构建、快速查找、数据...

    计算文件或者字符串HASH,SHA1,SHA256,CRC32,MD5值

    标题中的“计算文件或者字符串HASH,SHA1,SHA256,CRC32,MD5值”是指在信息技术领域中,用于验证数据完整性的几种常见的散列算法。这些算法能够将任意长度的数据转换为固定长度的唯一标识,常用于文件校验、数据安全...

    字符串哈希成数字的C实现的代码(含测试)

    将字符串哈希成数字的几种经典的方法:其中的一部分 #ifndef INCLUDE_GENERALHASHFUNCTION_C_H #define INCLUDE_GENERALHASHFUNCTION_C_H #include typedef unsigned int (*hash_function)(char*, unsigned int...

    各种字符串Hash函数比较1

    在IT领域,哈希函数是数据处理和存储中不可或缺的一部分,尤其在字符串处理时,哈希函数能够将任意长度的字符串映射成固定长度的数值,这个数值通常称为哈希值。哈希函数的设计目标是尽可能减少哈希冲突,即不同的...

    用C语言实现常用的字符串哈希函数

    用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等

    字符串的哈希Key算法

    字符串哈希Key算法是计算机科学中一种用于快速查找和存储字符串的重要技术。它通过将字符串转化为固定长度的数值,即哈希值,使得在大量数据中查找特定字符串变得高效。这种算法广泛应用于数据库索引、缓存系统、...

    字符串统计函数,统计不同字符个数和每个字符出现的次数

    在编程领域,字符串处理是一项常见的任务,特别是在数据分析、文本挖掘以及日志分析等场景中。字符串统计函数就是用于处理这类任务的重要工具。本篇将详细探讨如何实现一个统计字符串中不同字符个数以及每个字符出现...

    bcrypt库C/C++使用

    //此函数用于生成hash字符串 std::string hash = BCrypt::generateHash(password); //用于判断密码和数据库password加密后的字符串是否匹配 std::cout &lt;&lt; BCrypt::validatePassword(password,hash) &lt;&lt; std::...

Global site tag (gtag.js) - Google Analytics