題目鏈接：點擊查看

題目大意：給出n個字符串，現(xiàn)在需要將其依次合并，合并的規(guī)則是如果相鄰兩個字符串中的前后綴有相同的，則合并后省略掉后面字符串的前綴，我們需要保證這個相同的前后綴如果存在的情況下必須最大，輸出合并后的字符串

題目分析：可以直接哈希暴力然后string類合并，不過由于這是在cf，用哈希的一個弊端就是很容易被hack，我一開始用一直用的base131和ull寫了個單哈希，被test65卡住了，去網(wǎng)上搜了一下題解，發(fā)現(xiàn)大家基本上都是單哈希被卡住了，不過我找到了一個可以茍過去的數(shù)據(jù)：base=2333333，mod=999999998，這個可以單哈希茍過去，如果以后再遇到類似的問題，肯定直接三哈希起步了。。如果再被卡就繼續(xù)加嘛，反正寫好了一個哈希之后就可以直接CV大法了

最后感嘆一句，沒想到哈希還能倒著來，真的是學(xué)到了學(xué)到了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int mod=999999998;const int base=2333333;string s,ans;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);cin>>ans;for(int i=2;i<=n;i++){cin>>s;ull hash1=0,hash2=0,temp=1;int mark=0;for(int len=1;len<=min(ans.size(),s.size());len++)//枚舉長度 {hash1=(hash1*base+ans[ans.size()-len])%mod;hash2=(s[len-1]*temp+hash2)%mod;temp=temp*base%mod;if(hash1==hash2)mark=len;}ans+=s.substr(mark);}cout<<ans<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1200E Compress Words(字符串哈希)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。