하위 문자열 질문 - 문자hash 템플릿
990 단어 트레이닝 노트acm-문자 - 문자hash
베이스는 진법을 표시하고 실제 문제에 따라 수정할 수 있으며 xp[i]는 베이스 진법 아래의 상응하는 위치의 십진법을 표시한다.
#include
#include
using namespace std;
const int maxn=100001;
const int base=27;
typedef unsigned long long ull;
ull Hash[maxn];
ull xp[maxn];
int main()
{
xp[0]=1;
for(int i=1;i>a;
int L=a.length(),a_num=0;
for(int i=L-1;i>=0;i--)
a_num=a_num*base+a[i]-'a'+1;
string x;
cin>>x;
int len=x.length();
Hash[len]=1;
for(int i=len-1;i>=0;i--)
Hash[i]=Hash[i+1]*base+x[i]-'a'+1;
bool flag=false;
for(int i=0;i+L<=len;i++){
if(a_num==Hash[i]-Hash[i+L]*xp[L]){
printf("yes
");
flag=true;
}
}
if(!flag)printf("no
");
return 0;
}