正文

字符串HASH 学习总结 &&　模板

IP云
IP云V管理员/0 阅读
12/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

一、字符串HASH模板  取自挑战程序设计竞赛(第2版) 

</pre><pre code_snippet_id="446698" snippet_file_name="blog_20140809_1_9461278" name="code" class="cpp">/*===================================================*\

    从b串中寻找和a串长度同样的子串，返回開始位置

    不保证绝对正确，发生冲突概率为O(sqrt(n)),

    n为哈希函数的最大值

\*===================================================*/

#define ull unsigned long long

const ull B = 1e8+7;    /*according to the book*/

const int MAXN = 1001;

char a[MAXN],b[MAXN];

int HashFind()/*返回匹配位置的開始处的下标,-1表示没有匹配*/

{

    int al=strlen(a),bl=strlen(b);

    if(al>bl)return -1;

    ull t=1,ah=0,bh=0;

    for(int i=0;i<al;i++)

    {

        t*=B;

        ah=ah*B+a[i];

        bh=bh*B+b[i];

    }

    for(int i=0;i+al<=bl;i++)

    {

        if(ah == bh)return i;

        if(i+al < bl)bh=bh*B+b[i+al]-b[i]*t;

    }

    return -1;

}

/*===================================================*\

    滚动哈希--滚动通过ull的溢出实现,相当于mod 2^64

\*===================================================*/

#define ull unsigned long long

const int MAXN = 1001;

const ull B = 1e8+7;    /*according to the book*/

char a[MAXN],b[MAXN];

int OverLap()/*a的后缀和b的前缀相等的最大长度*/

{

    int al=strlen(a),bl=strlen(b),ans=0;

    int minlen=min(al,bl);

    ull t=1,ah=0,bh=0;

    for(int i=1;i<minlen;i++)

    {

        ah=ah+a[al-i]*t;

        bh=bh*B+b[i-1];

        if(ah == bh)ans=i;

        t*=B;

    }

    return ans;

}

二、字符串HASH的求法：（注意我不同颜色标记的地方，假设WA，一定看看那里是不是写对了）

1、直接ah[i]=ah[i-1]*base+a[i]，那么长度为len的哈希值就是ah[i]-ah[i-len]*base[len]  此处ah[i]表示长为i字符串的哈希值

北京邀请赛的题，为了能做到在O(1)时间内算出hash值---比方算从l到r这段字符串的hash值，能够直接ah[r]-ah[l-1]（当然须要推断l>=1，或者直接字符串从下标为1開始）。便于进行二分，就是这么写的

http://blog.csdn.net/u011026968/article/details/38473707

2、逐步递推：hash[i]=hash[i-1]*base+a[i]-a[i-len]*base[len]  再写字符矩阵匹配的时候两种写法我弄混了...o(╯□╰)o

三、HASH的其它构造方法：

1、假设限定了字符数目，能够映射为对应进制的数，如http://blog.csdn.net/u011026968/article/details/38490653

字符串HASH 学习总结 &amp;&amp;　模板的更多相关文章
  1. 字符串Hash学习笔记

    [toc] # 以下内容作废,太多错误了,等我有时间重写 说一下什么是Hash,说白了就是把一大坨字符用一些神奇的数来表示,可以说是把字符加密了. 简单一点就是一个像函数一样的东西,你放进去一个值,它 ...

  2. hdu 4622 Reincarnation 字符串hash 模板题

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意:给定一个长度不超过2000的字符串,之后有不超过1e5次的区间查询,输出每次查询区间中不同 ...

  3. cf244D. Match &amp; Catch 字符串hash （模板）或 后缀数组。。。

    D. Match & Catch 能够用各种方法做.字符串hash.后缀数组,dp.拓展kmp,字典树.. . 字符串hash(模板) http://blog.csdn.net/gdujian ...

  4. 字符串hash + 二分答案 - 求最长公共子串 --- poj 2774

    Long Long Message Problem's Link:http://poj.org/problem?id=2774 Mean: 求两个字符串的最长公共子串的长度. analyse: 前面在 ...

  5. HDU-魔咒词典(字符串hash)

    魔咒词典 TimeLimit: 8000/5000 MS (Java/Others)  MemoryLimit: 32768/32768 K (Java/Others) 64-bit integer ...

  6. 字符串hash入门

    简单介绍一下字符串hash 相信大家对于hash都不陌生 翻译过来就是搞砸,乱搞的意思嘛 hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法 在信息学奥 ...

  7. I - Magic FZU - 2280 （字符串hash）

    题目链接: I - Magic FZU - 2280 学习链接: FZU - 2280 I - Magic 题目大意: 给你nn个字符串,每个字符串有一个值ww,有qq次询问,一共两种操作:一是“1, ...

  8. Spring Boot学习记录(二)--thymeleaf模板 - CSDN博客

    ==他的博客应该不错,没有细看 Spring Boot学习记录(二)--thymeleaf模板 - CSDN博客 http://blog.csdn.net/u012706811/article/det ...

  9. 【字符串算法1】 再谈字符串Hash（优雅的暴力）

    [字符串算法1] 字符串Hash(优雅的暴力) [字符串算法2]Manacher算法 [字符串算法3]KMP算法 这里将讲述  [字符串算法1] 字符串Hash 老版原文: RK哈希(Rabin_Ka ...

随机推荐
  1. Contest Reviews(Updating)

    现在每天至少一套题又不太想写题解…… 那就开个坑总结下每场的失误和特定题目的技巧吧 2018.8.25[ZROI] T3传送门 T1:找规律找崩了…… 最好不要一上来就钻进大讨论,先想有没有普适规律 ...

  2. [ZHOJ1956]vfk的地雷

    题目大意: 有$n$个开关,$r$句话. 每个开关$i$有$p_i$的概率被触发,并造成$d_i$的代价. 每个开关至多被触发一次,一句话至多触发一个开关. 每个开关按照顺序被尝试触发. 求期望代价. ...

  3. hdu 5228 枚举

    题意:在前往ZJOI2015一试的路上,ZCC在同Fsygd打德州扑克时输光了所有的筹码.不过ZCC最近学会了一些黑技术.现在,他能够在游戏过程中更换任何他想要更换的牌.ZCC想要通过更换尽量少的牌得 ...

  4. TSQL update 简单应用小总结

    UPDATE 有两种基本的格式.一种是用静态数据来修改表,另一种是用其他表中的数据来修改表.下面是第一种格式: UPDATE #famousjaycees SET jc = 'Jhony cash', ...

  5. BZOJ 1003 物流运输trans dijstra+dp

    1003: [ZJOI2006]物流运输trans Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 3896  Solved: 1608[Submit] ...

  6. 获取数据库连接对象(线程ThreadLocal)

    /** * 负责数据库连接定义的程序类 * 该类可以负责所有操作线程的数据库连接,利用get()方法可以获得连接对象 */ public class DatabaseConnection { priv ...

  7. [Linux] tmux 终端复用命令行工具

    tmux 终端复用命令行工具 tmux 是一款终端复用命令行工具,通常用于 Terminal 的窗口管理.可以在终端软件重启后通过命令行恢复上次的 session. 安装运行 macOS 上使用 Ho ...

  8. Chrome DevTools Protocol Viewer

    Chrome DevTools Protocol Viewer     awesome-chrome-devtools

  9. sublime插件汇总

    JsFormat javascript格式化 有时从网上扒了人家的js代码来学习学习,打开发现被压缩了,这时就能够用JsFormat插件格式化js代码,恢复未压缩时候的排版,挺给力的.按快捷键Ctrl ...

  10. STM32 3.3V参考电压 TL431/MC1403/LM385

    TL431作为一个高性价比的常用分流式电压基准,有很广泛的用途. 图(1)是TL431的典型接法,输出一个固定电压值,计算公式是: Vout = ( (R1+R2) / R2 ) * 2.5 V 同时 ...

相关阅读

目录[+]