字符串哈希个人理解包括解决kmp问题

字符串哈希个人理解包括解决kmp问题

tmp=s[0];for(int i=1; s[i]!='\0'; i++){tmp=tmp*10+s[i];}

这样一来我们便可以求出字符串所代表的值。
但我们都知道求哈希值是不能重复的，所以我们的进制要尽可能地大而且要是个素数，通过看他人的代码，我发现13331就是个很好的进制数，但光有进制数还是不行，我们还需要一个数来对求出值的字符串数值取模，于是我们便可以使用
unsigned long long
这个函数。
这个函数的意义是对数值自动对2的64次方取模，这样便省去我们的时间。
通过使用函数可以方便我们的使用。
以下便是对单个字符串的值的获取

#include
using namespace std;
typedef unsigned long long ull;
ull B=13331;
ull tmp;//自动对2e64取模；
ull hashff(char s[])
{tmp=s[0];//每次都是直接取字符的acill码for(int i=1; s[i]!='\0'; i++){tmp=tmp*B+s[i];//最重要的部分，即每次都让前一部分乘进制然后加上本部分。}return tmp;//返回值。
}
int main()
{ios::sync_with_stdio(false);int m,n;char s[1000001];while(cin>>s){cout<<hashff(s)<<endl;}return 0;
}

但我们发现，如果只是去求字符串的值这样太浪费了，我们可以通过函数来取得从第一位到每一位的数值，这样也好理解，上面的代码便是从第一位到最后一位的取值，我们便可以设置个数组，把第一位到每一位的值存下来。

typedef unsigned long long ull;
ull hasht[1000001];
void hashf(char s[])
{hasht[0]=s[0];for(int i=1; s[i]!='\0'; i++){hasht[i]=hasht[i-1]*B+s[i];}
}

通过上面的函数我发现kmp所解决的问题可以用字符串哈希来解决，我们只要让第一个字符串的一段区域的哈希值等于下一段字符串的哈希值就行了，但我们怎么才能去求的一段区域的哈希值呢，我们还是从十进制来举例子，
比如123456，我们通过对第一位到最后一位哈希值的获取，我们获得

hasht[0]=1;
hasht[1]=12;
hasht[2]=123;
hasht[3]=1234;
hasht[4]=12345;
hasht[5]=123456;

如果我们想去求45，我们该怎么做呢，我们应该用12345-123*100，这样便可以求得45.
这时我们就可以借助一个数组，这个数组里面是记录进制的次方，通过这个数组便可以帮助我们来算出区域的哈希值。

ull power[1000001];power[0]=1;for(int i=1; i<1000000; i++)power[i]=power[i-1]*B;

具体函数如下

ull hashans(int l,int r)//l，r表示从l到r的哈希值。
{if(l==0)return hasht[r];//如果l已经是最左边了那就直接输出hasht[r]，因为这就是他的值。else return hasht[r]-hasht[l-1]*power[r-l+1];//最右边的哈希值减去从l到r相差了几个进制的次方再乘上从左边想左的值。
}

解决kmp完整代码如下：

#include
using namespace std;
typedef unsigned long long ull;
ull B=13331;
ull hasht[1000001],tmp,power[1000001],sum;
void hashf(char s[])
{hasht[0]=s[0];for(int i=1; s[i]!='\0'; i++){hasht[i]=hasht[i-1]*B+s[i];}
}
ull hashff(char s[])
{tmp=s[0];for(int i=1; s[i]!='\0'; i++){tmp=tmp*B+s[i];}return tmp;
}
ull hashans(int l,int r)
{if(l==0)return hasht[r];else return hasht[r]-hasht[l-1]*power[r-l+1];
}
int main()
{ios::sync_with_stdio(false);int m,n;char s[1000001],ss[1000001];power[0]=1;for(int i=1; i<1000000; i++)power[i]=power[i-1]*B;while(cin>>s){m=strlen(s);hashf(s);cin>>ss;n=strlen(ss);sum=hashff(ss);int i,flag=0;for(i=n-1; i<m; i++){if(sum==hashans(i-n+1,i)){flag=1;break;}}if(flag==1)cout<<i-n+2<<endl;else cout<<-1<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！