《算法笔记》12.1小节——字符串专题-＞字符串hash进阶 问题 A: 求最长公共子串（串）

题目描述

求采用顺序结构存储的串s和串t的一个最长公共子串，若没有则输出false，若最长的有多个则输出最先出现的那一串。

输入

输入两个字符串

输出

输出公共子串

样例输入

abcdef
adbcef

样例输出

bc

分析：用字符串哈希解决。检查子串的哈希值是否相等，如果相等，说明是公共子串。书上的模板代码只能求出最长长度，添加一个下标位置即可。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;typedef struct node
{int hashvalue,index;
}node;const long long mod=1e9+7;
const long long p=1e7+19;
const long long maxn=1010;
long long powp[maxn],h1[maxn],h2[maxn];
//vector<pair<int,int>>pr1,pr2;
vector<pair<node,int>>pr1,pr2;void init(int len)
{powp[0]=1;for(int i=1;i<=len;++i)powp[i]=powp[i-1]*p%mod;
}void calh(long long h[],string &str)
{h[0]=str[0];for(int i=1;i<str.length();++i)h[i]=(h[i-1]*p+str[i])%mod;
}int calsinglesubh(long long h[],int i,int j)
{if(i==0)return h[j];return ((h[j]-h[i-1]*powp[j-i+1])%mod+mod)%mod;
}void calsubh(long long h[],int len,vector<pair<node,int>>&pr)
{for(int i=0;i<len;++i){for(int j=0;j<len;++j){int hashvalue=calsinglesubh(h,i,j);
//            pr.push_back(make_pair(hashvalue,j-i+1));node temp;temp.hashvalue=hashvalue,temp.index=i;pr.push_back(make_pair(temp,j-i+1));}}
}int getmax()
{
//    int ans=0;int ans=0,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)
//                ans=max(ans,pr1[i].second);if(pr1[i].first.hashvalue==pr2[j].first.hashvalue){if(ans<pr1[i].second)ans=pr1[i].second,index=i;}}}
//    return ans;return index;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);clock_t start=clock();#endif //teststring str1,str2;getline(cin,str1);getline(cin,str2);init(max(str1.length(),str2.length()));calh(h1,str1);calh(h2,str2);calsubh(h1,str1.length(),pr1);calsubh(h2,str2.length(),pr2);
//    printf("ans=%d\n",getmax());int ind=getmax();if(ind==-1)printf("false\n");else{int index=pr1[ind].first.index,len=pr1[ind].second;for(int i=index,j=0;j<len;++i,++j)printf("%c",str1[i]);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}