定义结构体时,如果自己没有写构造函数,而是用的默认构造函数,则默认构造函数
   的参数顺序是与定义结构体时的变量顺序相同;

此下皆为看算法笔记所写:

问题一:

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};
}
*/

Logo

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

更多推荐