poj1200 Language: Crazy Search

xiaoxiao2021-02-28  6

poj1200 题意:求一个字符串中,长度为n的字串的种类

标准哈希【捂脸】..我的哈希…感觉…有待改进【捂脸】

#include <cstdio> #include <cstring> #define N 17000000 char s[N]; int ans=0,n,m,len,num=0,hash[N],flag[N]; unsigned long long sum=0,k=1; int main(){ scanf("%d%d%s",&n,&m,s+1);len=strlen(s+1); for(int i=1;i<=len;i++) if(!flag[s[i]]) flag[s[i]]=++num; for(int i=1;i<=n;i++) sum=sum*m+flag[s[i]]-1,k*=m; k/=m;hash[sum]=1;ans++; for(int i=n+1;i<=len;i++){ sum=(sum-(flag[s[i-n]]-1)*k)*m+flag[s[i]]-1; if(!hash[sum]) hash[sum]=1,ans++; }printf("%d\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1750106.html

最新回复(0)