Wannafly挑战赛11 D 题 字符串hash + 卡常

题目链接

https://ac.nowcoder.com/acm/contest/73#question

map与order_map

https://blog.csdn.net/BillCYJ/article/details/78985895

解析 先把T串的所有状态的hash值存在order_map里面  然后对于每一个模式串计算其每一个长度为len(T)的子串的hash值 若在order_map里面则ans++

这道题1e7的数据查找比较多map(O(log(n)) 查找会比 order_map( O(1) )慢 然后再卡卡常就可以了。。。正解是ex_kmp

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e6+;
const int base=; //base,基数 char s1[maxn],s2[maxn];
ull Hash[maxn],temp[maxn],power=; //记录主串哈希值的数组 int main()
{
scanf("%s",s1+); //从第一位开始输入
int n=strlen(s1+);
Hash[]=;
for(int i=;i<=n;i++)
{
s1[i+n]=s1[i];
power*=base;
Hash[i]=Hash[i-]*base+(ull)s1[i];
}
unordered_map<ull,int> ma;
for(int i=n+;i<=n+n;i++)
{
Hash[i]=Hash[i-]*base+(ull)s1[i];
ma[Hash[i]-Hash[i-n]*power]=;
}
int k;
scanf("%d",&k);
while(k--)
{
int ans=;
scanf("%s",s2+);
int m=strlen(s2+);
if(m<n)
{
printf("0\n");
continue;
}
temp[]=;
for(int i=;i<=m;i++)
{
temp[i]=temp[i-]*base+(ull)s2[i];
if(i>=n&&ma[temp[i]-temp[i-n]*power])
ans++;
}
printf("%d\n",ans);
}
return ;
}
上一篇:Rails内存的问题 Java内存情况


下一篇:Java IO 技术