[HDU 4821] String (字符串哈希)

时间:2022-09-20 22:51:19

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4821

题目大意:给你M,L两个字母,问你给定字串里不含M个长度为L的两两相同的子串有多少个?

哈希+枚举

我就是不会枚举这样的,这次涨姿势了。

每次枚举起点,然后就能枚举全部的。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull; const ull B = **+;
int M,L;
char s[];
ull h[];
ull base[];
ull tt[]; int main(){
base[] = ;
for(int i=;i<;i++) base[i] = base[i-]*B;
while(scanf("%d%d",&M,&L)!=EOF){
memset(h,,sizeof(h));
scanf("%s",s);
int len = strlen(s);
for(int i=;i<len;i++){
if( i== ) h[i] = s[i];
else h[i] = h[i-]*B + s[i];
}
int ans = ;
// printf("len = %d\n",len);
for(int i=;i<L;i++){ // 枚举全部起点
// puts("*******************");
int cnt = ;
map<ull,int> H;
for(int j=i;j+L<=len;j+=L){ // 枚举每段
tt[cnt++] = h[j+L-] - (j==?:(h[j-]*base[L]));
// printf("%d => %llu\n",j,tt[cnt-1]);
}
// printf("cnt=%d\n",cnt);
// 迟取法取每段然后数数,注意这里的j<min(cnt,M)
for(int j=;j<min(cnt,M);j++){
// printf("******%llu\n",H[tt[j]]);
H[tt[j]]++;
}
if( H.size()==M ){
ans++;
// printf("%d==%d\n",H.size(),M);
}
for(int j=M;j<cnt;j++){
H[tt[j-M]]--;
if( H[tt[j-M]]== ) H.erase(tt[j-M]);
H[tt[j]]++;
if( H.size()==M ){
ans++;
// printf("%d==%d\n",H.size(),M);
}
}
}
printf("%d\n",ans);
}
return ;
}

[HDU 4821] String (字符串哈希)的更多相关文章

  1. HDU 4821 String 字符串hash

    String Problem Description   Given a string S and two integers L and M, we consider a substring of S ...

  2. HDU 3973 AC&&num;39&semi;s String 字符串哈希

    HDU 3973 通过哈希函数将一个字符串转化为一个整数,通过特定的方式可以使得这个哈希值几乎没有冲突(这就是关键之处,几乎没有视为没有= =!, 其实也可以考虑实现哈希冲突时的处理,只是这道题没必要 ...

  3. HDU 4821 String(BKDRHash)

    http://acm.hdu.edu.cn/showproblem.php?pid=4821 题意:给出一个字符串,现在问你可以找出多少个长度为M*L的子串,该子串被分成L个段,并且每个段的字符串都是 ...

  4. HDU 4821 String(2013长春现场赛I题)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4821 字符串题. 现场使用字符串HASH乱搞的. 枚举开头! #include <stdio.h ...

  5. HDU 4821 String (HASH)

    题意:给你一串字符串s,再给你两个数字m l,问你s中可以分出多少个长度为m*l的子串,并且子串分成m个长度为l的串每个都不完全相同 首先使用BKDRHash方法把每个长度为l的子串预处理成一个数字, ...

  6. HDU 4821 String hash

    String Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/view.action ...

  7. HDU - 4821 String(窗口移动&plus;map去重&plus;hash优化)

    String Given a string S and two integers L and M, we consider a substring of S as “recoverable” if a ...

  8. TTTTTTTTTTTTTTTT hdu 5510 Bazinga 字符串&plus;哈希

    Bazinga Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Sub ...

  9. Hdu 4821 (字符串hash&plus;map)

    题目链接https://vjudge.net/problem/HDU-4821 题意:给定字符串S ,询问用几个子串满足 : 1.长度为n*len  . 2. n个子串都不相同. 题解:倒序hash将 ...

随机推荐

  1. java更改数据库中的数据

    不废话,上代码 package com.ningmeng; import java.sql.*; /** * 1:更改数据库中的数据 * @author biexiansheng * */ publi ...

  2. &period;NET Reflector 7&period;6&period;1&period;824 Edition &period;NET程序反编译神器&lpar;附插件安装教程2012-10-13更新&rpar; 完全破解&plus;使用教程

    原文来自VAllen cnblogs 一.使用教程1.解压后,双击Reflector.exe,如果有选择默认版本的.Net Framework,根据需要选择即可.你选择的版本不同则出现的默认程序集也不 ...

  3. 【转】loading 三种实现方式

    转载:http://www.eoeandroid.com/forum.php?mod=viewthread&tid=76872 一.通过动画实现 定义res/anim/loading.xml如 ...

  4. ubuntu sudo

    sudo(substitute user 或者 superuser do),是一种程序, 以允许用户通过安全的方式使用特殊的权限运行程序(通常为系统的超级 用户) 语法 sudo [-bhHpV][- ...

  5. uniq和sort的用法

    uniq和sort都是按行操作的linux命令. sort按文本行排序,如下所示的log文件:直接sort log即可将其排序. 容易忽略的是sort -n命令,在如下例子中将看到 如果直接sort则 ...

  6. Tomcat使用shutdown&period;bat关闭会将其他Tomcat关掉的问题

    Tomcat使用shutdown.bat关闭会将其他Tomcat关掉的问题 shutdown.bat文件有一句if not "%CATALINA_HOME%" == "& ...

  7. solidity高级理论&lpar;三&rpar;:时间单位与view

    solidity高级理论(三):时间单位与view 关键字:时间单位.view.Gas优化 solidity使用自己的本地时间单位 变量 now 将返回当前的unix时间戳(自1970年1月1日以来经 ...

  8. UVA 11624-Fire&excl;【双BFS】

    <题目链接> 题目大意: 你的任务是帮助J走出一个大火蔓延的迷宫.J每分钟可以超上下左右四个方向移动,而所有着火的格子每一分钟都会往四个方向蔓延一格.迷宫中有一些障碍,J和火都无法进入.当 ...

  9. 轻量级RPC

    ①自定义一个协议接口继承VersionedProtocol ②自定义协议类实现上面的接口,完善功能需求 ③服务端 ④客户端 二:模拟一个namenode

  10. spring中MessageSource的配置使用方法3--ResourceBundleMessageSource【转】

    本文转载仅供自己学习收录,不做任何商业用途,如有需要请访问原地址:http://blog.csdn.net/qyf_5445/article/details/8124431 ApplicationCo ...