题目链接: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 (字符串哈希)的更多相关文章
-
HDU 4821 String 字符串hash
String Problem Description Given a string S and two integers L and M, we consider a substring of S ...
-
HDU 3973 AC&#39;s String 字符串哈希
HDU 3973 通过哈希函数将一个字符串转化为一个整数,通过特定的方式可以使得这个哈希值几乎没有冲突(这就是关键之处,几乎没有视为没有= =!, 其实也可以考虑实现哈希冲突时的处理,只是这道题没必要 ...
-
HDU 4821 String(BKDRHash)
http://acm.hdu.edu.cn/showproblem.php?pid=4821 题意:给出一个字符串,现在问你可以找出多少个长度为M*L的子串,该子串被分成L个段,并且每个段的字符串都是 ...
-
HDU 4821 String(2013长春现场赛I题)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4821 字符串题. 现场使用字符串HASH乱搞的. 枚举开头! #include <stdio.h ...
-
HDU 4821 String (HASH)
题意:给你一串字符串s,再给你两个数字m l,问你s中可以分出多少个长度为m*l的子串,并且子串分成m个长度为l的串每个都不完全相同 首先使用BKDRHash方法把每个长度为l的子串预处理成一个数字, ...
-
HDU 4821 String hash
String Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/view.action ...
-
HDU - 4821 String(窗口移动+map去重+hash优化)
String Given a string S and two integers L and M, we consider a substring of S as “recoverable” if a ...
-
TTTTTTTTTTTTTTTT hdu 5510 Bazinga 字符串+哈希
Bazinga Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Sub ...
-
Hdu 4821 (字符串hash+map)
题目链接https://vjudge.net/problem/HDU-4821 题意:给定字符串S ,询问用几个子串满足 : 1.长度为n*len . 2. n个子串都不相同. 题解:倒序hash将 ...
随机推荐
-
java更改数据库中的数据
不废话,上代码 package com.ningmeng; import java.sql.*; /** * 1:更改数据库中的数据 * @author biexiansheng * */ publi ...
-
.NET Reflector 7.6.1.824 Edition .NET程序反编译神器(附插件安装教程2012-10-13更新) 完全破解+使用教程
原文来自VAllen cnblogs 一.使用教程1.解压后,双击Reflector.exe,如果有选择默认版本的.Net Framework,根据需要选择即可.你选择的版本不同则出现的默认程序集也不 ...
-
【转】loading 三种实现方式
转载:http://www.eoeandroid.com/forum.php?mod=viewthread&tid=76872 一.通过动画实现 定义res/anim/loading.xml如 ...
-
ubuntu sudo
sudo(substitute user 或者 superuser do),是一种程序, 以允许用户通过安全的方式使用特殊的权限运行程序(通常为系统的超级 用户) 语法 sudo [-bhHpV][- ...
-
uniq和sort的用法
uniq和sort都是按行操作的linux命令. sort按文本行排序,如下所示的log文件:直接sort log即可将其排序. 容易忽略的是sort -n命令,在如下例子中将看到 如果直接sort则 ...
-
Tomcat使用shutdown.bat关闭会将其他Tomcat关掉的问题
Tomcat使用shutdown.bat关闭会将其他Tomcat关掉的问题 shutdown.bat文件有一句if not "%CATALINA_HOME%" == "& ...
-
solidity高级理论(三):时间单位与view
solidity高级理论(三):时间单位与view 关键字:时间单位.view.Gas优化 solidity使用自己的本地时间单位 变量 now 将返回当前的unix时间戳(自1970年1月1日以来经 ...
-
UVA 11624-Fire!【双BFS】
<题目链接> 题目大意: 你的任务是帮助J走出一个大火蔓延的迷宫.J每分钟可以超上下左右四个方向移动,而所有着火的格子每一分钟都会往四个方向蔓延一格.迷宫中有一些障碍,J和火都无法进入.当 ...
-
轻量级RPC
①自定义一个协议接口继承VersionedProtocol ②自定义协议类实现上面的接口,完善功能需求 ③服务端 ④客户端 二:模拟一个namenode
-
spring中MessageSource的配置使用方法3--ResourceBundleMessageSource【转】
本文转载仅供自己学习收录,不做任何商业用途,如有需要请访问原地址:http://blog.csdn.net/qyf_5445/article/details/8124431 ApplicationCo ...