字符串hash进阶,将字符串转化为数字存到数组中
此下皆为看算法笔记所写:问题一:1)给定若干个个字符串,求有多少个不同的字符串/*1)给定若干个个字符串,求有多少个不同的字符串*/#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;typedef long long
定义结构体时,如果自己没有写构造函数,而是用的默认构造函数,则默认构造函数
的参数顺序是与定义结构体时的变量顺序相同;
此下皆为看算法笔记所写:
问题一:
1)给定若干个个字符串,求有多少个不同的字符串
/*1)给定若干个个字符串,求有多少个不同的字符串*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
LL hashfunc(string str);
const int P=1e7+19;
const int mod=1e9+7;
int main()
{
string str;
vector<int> ans;
while(getline(cin,str),str!="#")
{
LL id=hashfunc(str);
ans.push_back(id);
}
sort(ans.begin(),ans.end());
int count=0;
for(size_t i=0;i<ans.size();++i)
{
cout << ans[i] << endl;
if(i==0||ans[i]!=ans[i-1])
++count;
}
cout << count << endl;
return 0;
}
LL hashfunc(string str)
{
LL H=0;
for(size_t i=0;i<str.size();++i)
H=(H*P+str[i]-'a')%mod;
return H;
}
接着问题升级:
2)求解字符串的子串的hash值
H[i]=H[i-1]*P+index(str[i])
H[i...j]=index(str[i])*P^(j-i)+index(str[i+1])*P^(j-i-1)+...+index(str[j])*P^0;
H[j]=H[j-1]*P+index(str[j])
=((H[j-2]*P+index(str[j-1]))*P)+index(str[j])
=......
=H[j-2]*P^2+index(str[j-1])*P+index(str[j])
=H[i-1]*P^(j-(i-1))+index(str[i])*P^(j-i)+index(str[i+1])*P^(j-i-1)+...+index(str[j])*P^0
=H[i-1]*P^(j-i+1)+H[i...j]
-> H[i...j]=H[j]-H[i-1]*P^(j-i+1)
SO 为了得到正数:
H[i...j]=(H[j]-H[i-1]*P^(j-i+1)%mod+mod)%mod;
其中:H[i]表示str的第一位到第i位的子串的hash值
题目来了:
问题:输入两个长度不超过1000的字符串,求他们的最长公共子串的长度?
分析:可以求出两个字符串的子串的hash值,并记录对应长度,最后一一比较
每个子串的hash值是否相等,并比较长度
那么就可以用一个pair<int,int>存储每个子串的hash值及对应的长度,把每个字符串
的各个子串的pair存储到一个vector容器中。
这是书上给出的代码的问题,但是当我们要求解输出公共子串本身怎么办,显然,vector中再加一个值,存储子串在字符串中的下标便可。由于存储三个值,定义一个结构体显然是最好的选择,当然,我开始没想到,看了一个哥们的博客才知道了。我最开始想的是vector中,存一个pair,pair的第一个类型是一个int,存储子串hash值,第二个又是一个pair,其中两个类型都是int,第一个存储子串长度,第二个存储子串在原字符串中下标的值。想来也是,pair在结构体只有两个元素时,可以代替,但多于两个,最好定义结构体较为方便。我最开始便是求最长子串的函数发生了一点错误,没能发现,便百度了。及下面这句代码,第二个for循环的条件部分,为何会用it1去比较,现在细想,发生段错误,便是在这儿。可这错误也是极难发现,寻找出来的。
for(auto it1=pr1.begin();it1!=pr1.end();++it1)
for(auto it2=pr2.begin();it1!=pr2.end();++it2)
用hash数组解决字符串问题时,莫过于需要这几个函数:
void init_powP(int len); //计算powP[]的值
void hashfunc(string str,LL *H);//计算H[i]的值
int str_sub_hash(LL *H,int i,int j); //计算H[i...j]的值
void cal_str_sub_pair(vector<Node> &pr,LL *H,int len); //将子串的hash值,长度,起始位置存到pr数组中
Node getmax(); //返回最大公共子串的长度及起始位置
/**
solution one:只输出了最大公共子串的长度:
这是一个错误代码;下面给出了原因;
一个pair<int,int>存储每个子串的hash值及对应的长度,把每个字符串
的各个子串的pair存储到一个vector容器中。
但存在一个问题,显而易见,由于int最大能表示的值为21亿,大概是1e9,
而P*mod等于1e16,显然不能正确存储,long long型能存储1e19,远远足够。
所以存储hash值的数组需要开成long long类型;
其实也可以避免错误:在后面的程序中判断两个int相乘是否
会溢出,如果会溢出,则要把其中一个int强制转换为long long,也就是在
str_sub_hash 函数的else语句改变一下即可;
*/
/**
solution one:只输出了最大公共子串的长度:
这是一个错误代码;下面给出了原因;
一个pair<int,int>存储每个子串的hash值及对应的长度,把每个字符串
的各个子串的pair存储到一个vector容器中。
但存在一个问题,显而易见,由于int最大能表示的值为21亿,大概是1e9,
而P*mod等于1e16,显然不能正确存储,long long型能存储1e19,远远足够。
所以存储hash值的数组需要开成long long类型;
其实也可以避免错误:在后面的程序中判断两个int相乘是否
会溢出,如果会溢出,则要把其中一个int强制转换为long long,也就是在
str_sub_hash 函数的else语句改变一下即可;
*/
/**
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
void init_powP(int len);
void hashfunc(string str,int *H);
int str_sub_hash(int *H,int i,int j);
void cal_str_sub_pair(vector<pair<int,int> > &pr,int *H,int len);
int getmax();
const int P=1e7+19;
const int mod=1e9+7;
const int maxn=1001;
vector<pair<int,int> >pr1,pr2;
int H1[maxn],H2[maxn],powP[maxn];
int main()
{
string str1,str2;
getline(cin,str1);
getline(cin,str2);
int len=max(str1.size(),str2.size());
init_powP(len);
hashfunc(str1,H1);
hashfunc(str2,H2);
cal_str_sub_pair(pr1,H1,str1.size());
cal_str_sub_pair(pr2,H2,str2.size());
int max_len=getmax();
cout << max_len << endl;
return 0;
}
void init_powP(int len)
{
powP[0]=1;
for(int i=1;i<=len;++i)
powP[i]=(powP[i-1]*P)%mod;
}
void hashfunc(string str,int *H)
{
H[0]=str[0]-'a';
for(size_t i=1;i<str.size();++i)
H[i]=(H[i-1]*P+str[i]-'a')%mod;
}
int str_sub_hash(int *H,int i,int j)
{
if(i==0)
return H[j]%mod;
else
return ((H[j]-H[i-1]*powP[j-i+1])%mod+mod)%mod;
}
void cal_str_sub_pair(vector<pair<int,int> > &pr,int *H,int len)
{
for(int i=0;i<len;++i)
{
for(int j=i;j<len;++j)
{
int hash_value=str_sub_hash(H,i,j);
pr.push_back(make_pair(hash_value,j-i+1));
}
}
}
int getmax()
{
int ans=-1;
for(int i=0;i<pr1.size();++i)
for(int j=0;j<pr2.size();++j)
{
if(pr1[i].first==pr2[j].first)
ans=max(ans,pr1[i].second);
}
return ans;
}
*/
solution two:solution one:只输出了最大公共子串的长度:
/**
solution two:solution one:只输出了最大公共子串的长度:
*/
/**
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
void init_powP(int len);
void hashfunc(string str,LL *H);
int str_sub_hash(LL *H,int i,int j);
void cal_str_sub_pair(vector<pair<int,int> > &pr,LL *H,int len);
int getmax();
const LL P=1e7+19; //显而易见,由于int最大能表示的值为21亿,大概是1e9,而P*mod等于1e16,显然不能正确存储;
const LL mod=1e9+7; //long long型能存储1e19,远远足够。
const LL maxn=1001;
vector<pair<int,int> >pr1,pr2;
LL H1[maxn]={0},H2[maxn]={0},powP[maxn];
int main()
{
cout << ((1<<31)-1) << endl;
cout << ((1ll<<63)-1) << endl;
string str1,str2;
getline(cin,str1);
getline(cin,str2);
int len=max(str1.size(),str2.size());
init_powP(len);
hashfunc(str1,H1);
hashfunc(str2,H2);
cal_str_sub_pair(pr1,H1,str1.size());
cal_str_sub_pair(pr2,H2,str2.size());
int max_len=getmax();
cout << max_len << endl;
return 0;
}
void init_powP(int len)
{
powP[0]=1;
for(int i=1;i<=len;++i)
powP[i]=(powP[i-1]*P)%mod;
}
void hashfunc(string str,LL *H) //H[i]必然表示str的第一位到第i位的子串的hash值
{
H[0]=str[0]-'a';
for(size_t i=1;i<str.size();++i)
H[i]=(H[i-1]*P+str[i]-'a')%mod;
}
int str_sub_hash(LL *H,int i,int j)
{
if(i==0)
return H[j]%mod;
else
return ((H[j]-H[i-1]*powP[j-i+1])%mod+mod)%mod;
}
void cal_str_sub_pair(vector<pair<int,int> > &pr,LL *H,int len)
{
for(int i=0;i<len;++i)
{
for(int j=i;j<len;++j)
{
int hash_value=str_sub_hash(H,i,j);
pr.push_back(make_pair(hash_value,j-i+1));
}
}
}
int getmax()
{
int ans=-1;
for(int i=0;i<pr1.size();++i)
for(int j=0;j<pr2.size();++j)
{
if(pr1[i].first==pr2[j].first)
ans=max(ans,pr1[i].second);
}
return ans;
}
*/
solution three:输出公共子串本身;
想要输出公共子串本身,那么只存储子串的hash值,以及子串的长度是不够的,
还需要存储子串的起始位置;
用pair解决
/**
solution three:输出公共子串本身;
想要输出公共子串本身,那么只存储子串的hash值,以及子串的长度是不够的,
还需要存储子串的起始位置;
用pair解决
*/
/**
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
void init_powP(int len);
void hashfunc(string str,LL *H);
int str_sub_hash(LL *H,int i,int j);
void cal_str_sub_pair(vector<pair<int,pair<int,int> > > &pr,LL *H,int len);
pair<int,int> getmax();
const LL P=1e7+19; //显而易见,由于int最大能表示的值为21亿,大概是1e9,而P*mod等于1e16,显然不能正确存储;
const LL mod=1e9+7; //long long型能存储1e19,远远足够。
const LL maxn=1001;
vector<pair<int,pair<int,int> > >pr1,pr2;
LL H1[maxn]={0},H2[maxn]={0},powP[maxn];
pair<int,int> fac();
int main()
{
string str1,str2;
getline(cin,str1);
getline(cin,str2);
int len=max(str1.size(),str2.size());
init_powP(len);
hashfunc(str1,H1);
hashfunc(str2,H2);
cal_str_sub_pair(pr1,H1,str1.size());
cal_str_sub_pair(pr2,H2,str2.size());
pair<int,int> ans=getmax();
cout << "hello world\n";
if(ans.first==-1)
cout << "No common substr\n";
else
{
cout << ans.first << endl;
cout << str1.substr(ans.second,ans.first) << endl;
}
return 0;
}
void init_powP(int len)
{
powP[0]=1;
for(int i=1;i<=len;++i)
powP[i]=(powP[i-1]*P)%mod;
}
void hashfunc(string str,LL *H) //H[i]必然表示str的第一位到第i位的子串的hash值
{
H[0]=str[0]-'a';
for(size_t i=1;i<str.size();++i)
H[i]=(H[i-1]*P+str[i]-'a')%mod;
}
int str_sub_hash(LL *H,int i,int j)
{
if(i==0)
return H[j]%mod;
else
return ((H[j]-H[i-1]*powP[j-i+1])%mod+mod)%mod;
}
void cal_str_sub_pair(vector<pair<int,pair<int,int> > > &pr,LL *H,int len)
{
for(int i=0;i<len;++i)
{
for(int j=i;j<len;++j)
{
int hash_value=str_sub_hash(H,i,j);
pair<int,int> temp(j-i+1,i);
pr.push_back(make_pair(hash_value,temp));
}
}
}
////getmax第一种写法:
//pair<int,int> getmax()
//{
// int ans=-1,index=-1;
// for(auto &it1:pr1)
// {
// for(auto &it2:pr2)
// {
// if(it1.first==it2.first)
// {
// if(it1.second.first>ans)
// {
// ans=it1.second.first;
// index=it1.second.second;
// }
// break;
// }
// }
// }
// return make_pair(ans,index);
//}
//
//
// // getmax第二种写法:
//pair<int,int> getmax()
//{
// int ans=-1,index=-1;
// for(vector<pair<int,pair<int,int> > >::iterator it1=pr1.begin();it1!=pr1.end();++it1)
// for(vector<pair<int,pair<int,int> > >::iterator it2=pr2.begin();it2!=pr2.end();++it2)
// {
// if(it1->first==it2->first)
// if(it1->second.first>ans)
// {
// ans=it1->second.first;
// index=it1->second.second;
// }
// }
// return make_pair(ans,index);
//}
//getmax第三种写法:
pair<int,int> getmax()
{
int ans=-1,index=-1;
for(int i=0;i<pr1.size();++i)
for(int j=0;j<pr2.size();++j)
{
if(pr1[i].first==pr2[j].first)
if(pr1[i].second.first>ans)
{
ans=pr1[i].second.first;
index=pr1[i].second.second;
}
}
return make_pair(ans,index);
}
*/
solution three:结构体尝试;
将子串hash值,子串长度及子串起始位置都用结构体存储;
void init_powP(int len); //计算powP[]的值
void hashfunc(string str,LL *H);//计算H[i]的值
int str_sub_hash(LL *H,int i,int j); //计算H[i...j]的值
void cal_str_sub_pair(vector<Node> &pr,LL *H,int len); //将子串的hash值,长度,起始位置存到pr数组中
Node getmax(); //返回最大公共子串的长度及起始位置
/**
solution three:结构体尝试;
将子串hash值,子串长度及子串起始位置都用结构体存储;
*/
/**
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
struct Node
{
int hash_value,len,start;
Node(int a,int b,int c):hash_value(a),len(b),start(c){}
};
void init_powP(int len); //计算powP[]的值
void hashfunc(string str,LL *H);//计算H[i]的值
int str_sub_hash(LL *H,int i,int j); //计算H[i...j]的值
void cal_str_sub_pair(vector<Node> &pr,LL *H,int len); //将子串的hash值,长度,起始位置存到pr数组中
Node getmax(); //返回最大公共子串的长度及起始位置
const LL P=1e7+19; //显而易见,由于int最大能表示的值为21亿,大概是1e9,而P*mod等于1e16,显然不能正确存储;
const LL mod=1e9+7; //long long型能存储1e19,远远足够。
const LL maxn=1001;
vector<Node>pr1,pr2;
LL H1[maxn]={0},H2[maxn]={0},powP[maxn];
int main()
{
string str1,str2;
getline(cin,str1);
getline(cin,str2);
int len=max(str1.size(),str2.size());
init_powP(len);
hashfunc(str1,H1);
hashfunc(str2,H2);
cal_str_sub_pair(pr1,H1,str1.size());
cal_str_sub_pair(pr2,H2,str2.size());
Node ans=getmax();
cout << "hello world\n";
if(ans.len==-1)
cout << "No common substr\n";
else
{
cout << ans.len << endl;
cout << str1.substr(ans.start,ans.len) << endl;
}
return 0;
}
void init_powP(int len)
{
powP[0]=1;
for(int i=1;i<=len;++i)
powP[i]=(powP[i-1]*P)%mod;
}
void hashfunc(string str,LL *H) //H[i]必然表示str的第一位到第i位的子串的hash值
{
H[0]=str[0]-'a';
for(size_t i=1;i<str.size();++i)
H[i]=(H[i-1]*P+str[i]-'a')%mod;
}
int str_sub_hash(LL *H,int i,int j)
{
if(i==0)
return H[j]%mod;
else
return ((H[j]-H[i-1]*powP[j-i+1])%mod+mod)%mod;
}
void cal_str_sub_pair(vector<Node> &pr,LL *H,int len)
{
for(int i=0;i<len;++i)
{
for(int j=i;j<len;++j)
{
int hash_value=str_sub_hash(H,i,j);
pr.push_back(Node(hash_value,j-i+1,i));
}
}
}
Node getmax()
{
int ans=-1,index=-1;
for(int i=0;i<pr1.size();++i)
for(int j=0;j<pr2.size();++j)
{
if(pr1[i].hash_value==pr2[j].hash_value)
if(pr1[i].len>ans)
{
ans=pr1[i].len;
index=pr1[i].start;
}
}
return Node(1,ans,index);
}
*/
下面的代码是我后面重新写的,思想和上面的一样:
再编码:
H[i...j]=H[j]-H[i-1]*P^(j-i+1);
结构体存储子串hash值,长度,开始位置;
并且hash数组需要开到long long型;
/**
再编码:
H[i...j]=H[j]-H[i-1]*P^(j-i+1);
结构体存储子串hash值,长度,开始位置;
并且hash数组需要开到long long型;
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long LL;
struct Node
{
int val,len,start;
};
const int maxn=1010;
const LL P=1e7+19,mod=1e9+7;
LL powP[maxn],H1[maxn],H2[maxn];
void init(int len);
void hashfunc(string &str,LL *H);
int hash_sub(LL *H,int l,int r);
void cal_hash_sub(string &str,vector<Node> &ptr,LL *H);
Node max_len(vector<Node> &ptr1,vector<Node> &ptr2);
int main()
{
string str1,str2;
cin >> str1 >> str2;
int len=max(str1.size(),str2.size());
init(len);
hashfunc(str1,H1);
hashfunc(str2,H2);
vector<Node> ptr1,ptr2;
cal_hash_sub(str1,ptr1,H1);
cal_hash_sub(str2,ptr2,H2);
Node ans=max_len(ptr1,ptr2);
if(ans.len==-1)
printf("Imposible\n");
else
{
printf("公共子串的最长长度是%d\n",ans.len);
printf("最长长度的公共子串是:%s",str1.substr(ans.start,ans.len).c_str());
}
return 0;
}
void init(int len)
{
powP[0]=1;
for(int i=1;i<len;++i)
{
powP[i]=(powP[i-1]*P)%mod;
}
}
void hashfunc(string &str,LL *H)
{
H[0]=str[0]-'a';
for(int i=1;i<str.size();++i)
{
H[i]=(H[i-1]*P+str[i]-'a')%mod;
}
}
int hash_sub(LL *H,int l,int r)
{
if(l==0)
return H[r]%mod;
else
return ((H[r]-H[l-1]*powP[r-l+1])%mod+mod)%mod;
}
void cal_hash_sub(string &str,vector<Node> &ptr,LL *H)
{
for(int i=0;i<str.size();++i)
for(int j=i;j<str.size();++j)
{
int val=hash_sub(H,i,j);
ptr.push_back({val,j-i+1,i});
}
}
Node max_len(vector<Node> &ptr1,vector<Node> &ptr2)
{
int start=-1,len=-1;
for(auto val1:ptr1)
for(auto val2:ptr2)
{
if(val1.val==val2.val&&val1.len>len)
{
len=val1.len;
start=val1.start;
}
}
return Node{-1,len,start};
}
hahs数组定义为int型;
还是尽量把hash数组开到long long型,不然就要在后面的程序中判断两个int相乘是否
会溢出,如果会溢出,则要把其中一个int强制转换为long long,否则会出错;
定义结构体时,如果自己没有写构造函数,而是用的默认构造函数,则默认构造函数
的参数顺序是以定义结构体时的变量顺序相同;
/**
hahs数组定义为int型;
还是尽量把hash数组开到long long型,不然就要在后面的程序中判断两个int相乘是否
会溢出,如果会溢出,则要把其中一个int强制转换为long long,否则会出错;
定义结构体时,如果自己没有写构造函数,而是用的默认构造函数,则默认构造函数
的参数顺序是以定义结构体时的变量顺序相同;
*/
/**
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long LL;
struct Node
{
int val,len,start;
};
const int maxn=1010;
const LL P=1e7+19,mod=1e9+7;
int powP[maxn],H1[maxn],H2[maxn];
void init(int len);
void hashfunc(string &str,int *H);
int hash_sub(int *H,int l,int r);
void cal_hash_sub(string &str,vector<Node> &ptr,int *H);
Node max_len(vector<Node> &ptr1,vector<Node> &ptr2);
int main()
{
string str1,str2;
cin >> str1 >> str2;
int len=max(str1.size(),str2.size());
init(len);
hashfunc(str1,H1);
hashfunc(str2,H2);
vector<Node> ptr1,ptr2;
cal_hash_sub(str1,ptr1,H1);
cal_hash_sub(str2,ptr2,H2);
Node ans=max_len(ptr1,ptr2);
if(ans.len==-1)
printf("Imposible\n");
else
{
printf("公共子串的最长长度是%d\n",ans.len);
printf("最长长度的公共子串是:%s",str1.substr(ans.start,ans.len).c_str());
}
return 0;
}
void init(int len)
{
powP[0]=1;
for(int i=1;i<len;++i)
{
powP[i]=(powP[i-1]*P)%mod;
}
}
void hashfunc(string &str,int *H)
{
H[0]=str[0]-'a';
for(int i=1;i<str.size();++i)
{
H[i]=(H[i-1]*P+str[i]-'a')%mod;
}
}
int hash_sub(int *H,int l,int r)
{
if(l==0)
return H[r]%mod;
else
return ((H[r]-(LL)H[l-1]*powP[r-l+1])%mod+mod)%mod;
} //还是尽量把hash数组开到long long型,不然就要在这儿把int强制转换为long long,否则会溢出
void cal_hash_sub(string &str,vector<Node> &ptr,int *H)
{
for(int i=0;i<str.size();++i)
for(int j=i;j<str.size();++j)
{
int val=hash_sub(H,i,j);
ptr.push_back({val,j-i+1,i});
}
}
Node max_len(vector<Node> &ptr1,vector<Node> &ptr2)
{
int start=-1,len=-1;
for(auto val1:ptr1)
for(auto val2:ptr2)
{
if(val1.val==val2.val&&val1.len>len)
{
len=val1.len;
start=val1.start;
}
}
return Node{-1,len,start};
}
*/

GitCode 天启AI是一款由 GitCode 团队打造的智能助手,基于先进的LLM(大语言模型)与多智能体 Agent 技术构建,致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话,还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力,真正做到“一句话,让 Al帮你完成复杂任务”。
更多推荐
所有评论(0)