HDOJ--4821--String【弦hash】
string -- HASH hdoj
2023-09-14 09:08:04 时间
联系:http://acm.hdu.edu.cn/showproblem.php?pid=4821
题意:给一个字符串,选m个长度为l的子串组成新的串。要求这m个子串互不同样,问有多少种组合。
字符串hash题目,曾经没做过,做这道之前还用bkdrhash做了两道简单的题目。POJ1200和HDU1800。
用base数组记录乘了几个seed,base[i]表示seed^i,这个数组在之后计算子串hash值的时候会用到,先预处理一遍节省时间。
假设字符串从前往后hash。则hash[ i ] - hash[ i - l ] * base[ l ] 就是子串 [ i - l , i ] 的hash值,而从后往前hash的话 hash[ i ] - hash[ i + l ] * base[ l ] 就是子串 [ i , i + l ] 的hash值。
推导过程:以从前往后hash为例。如果字符串abab,子串长度2。则
i = 4时的hash值( ( ( (0+a)*seed+b ) * seed +a ) * seed + b ) ,
i - l = 2的hash值( (0+a)*seed+b )。乘base[2]之后 ( ( ( (0+a)*seed+b ) * seed ) * seed )
二者相减为a * seed + b。就是区间 [ i - l, i ] 相应字母 ab 的hash值。
之后依照每一点枚举m个l长度的子串,当他们hash值不同一时候就是一个结果。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 100010 #define eps 1e-7 #define INF 0x7FFFFFFF #define seed 131 typedef long long ll; typedef unsigned long long ull; char s[MAXN]; ull base[MAXN],Hash[MAXN]; map<ull,int> mp; int main(){ int m,l,i,len,ans; base[0] = 1; for(i=1;i<MAXN;i++) base[i] = base[i-1] * seed; while(scanf("%d%d",&m,&l)!=EOF){ scanf("%s",s); ans = 0; len = strlen(s); Hash[len] = 0; for(i=len-1;i>=0;i--){ Hash[i] = Hash[i+1] * seed + s[i] - 'a'; } for(i=0;i<l&&i+m*l<len;i++){ mp.clear(); for(int j=i;j<i+m*l;j+=l){ ull temp = Hash[j] - Hash[j+l] * base[l]; mp[temp]++; } if(mp.size()==m) ans++; for(int j=i+m*l;j+l<=len;j+=l){ ull temp = Hash[j-m*l] - Hash[j-(m-1)*l] * base[l]; mp[temp]--; if(!mp[temp]) mp.erase(temp); temp = Hash[j] - Hash[j+l] * base[l]; mp[temp]++; if(mp.size()==m) ans++; } } printf("%d\n",ans); } return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
相关文章
- java map 转string_java-将Map <String,Object>转换为Map <String,String>
- String头文件_string头文件的作用
- 【地铁上的Redis与C#】数据类型--string类型数据的扩展操作
- 【Android 应用开发】Android开发技巧--Application, ListView排列,格式化浮点数,string.xml占位符,动态引用图片
- 【C++修炼之路】9. string类的模拟实现
- ORA-00372: file string cannot be modified at this time ORACLE 报错 故障修复 远程处理
- ORA-23533: object “string”.”string” can not be cached ORACLE 报错 故障修复 远程处理
- ORA-25285: Invalid value string for array_mode ORACLE 报错 故障修复 远程处理
- ORA-26687: no instantiation SCN provided for “string”.”string” in source database “string” ORACLE 报错 故障修复 远程处理
- ORA-29336: Internal error [string] [string] from DBMS_PLUGTS ORACLE 报错 故障修复 远程处理
- ORA-29510: name, string.string, already used by an existing object ORACLE 报错 故障修复 远程处理
- ORA-31481: change source string is not a HotLog change source ORACLE 报错 故障修复 远程处理
- ORA-31640: unable to open dump file “string” for read ORACLE 报错 故障修复 远程处理
- ORA-39237: Failed to load XML document string. Compare process aborted. ORACLE 报错 故障修复 远程处理
- ORA-40213: contradictory values for settings: string, string ORACLE 报错 故障修复 远程处理
- ORA-47203: error deleting Integration Policy Factor for factor string and policy string, string ORACLE 报错 故障修复 远程处理
- ORA-47261: Realm Authorization to string for Realm string not found ORACLE 报错 故障修复 远程处理
- ORA-00330: archived log ends at change string, need change string ORACLE 报错 故障修复 远程处理
- ORA-16549: invalid string ORACLE 报错 故障修复 远程处理
- MySQL中String的使用方法和注意事项(mysql中string)
- c#中String和string的区别介绍