題目鏈接：點擊查看

題目大意：給出 n 個字符串，定義函數(shù) f( s , t ) 為字符串 s 的前綴和字符串 t 的后綴所能匹配的最大長度，現(xiàn)在求?

題目分析：因為總的前綴和后綴的個數(shù)都為??個，所以我們可以預(yù)處理時將所有的后綴的哈希扔到 map 里計數(shù)，然后遍歷每個前綴，記錄和當(dāng)前前綴相等的后綴有多少個，不過會出現(xiàn)重復(fù)計算的問題，例如對于字符串 s = "aba"?來說，f ( s?, s?) 應(yīng)該是 3 才對，但是當(dāng)長度為 1 時，s[ 1 ] = s[ 3 ] = ' a ' 因為也滿足前綴和后綴相等的條件，所以也會被計算到答案中去，為了去重，我們可以用 next 進(jìn)行去重，只需要使得 cnt[ next[ i ] ] -= cnt[ i ] 即可，具體原理自己在紙上畫一下不難看出，這里不多贅述了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;const int mod=998244353;map<ull,int>mp;string s[N];int nt[N*10],cnt[N*10];void Hash(string& s) {ull hash=0,p=1;for(int i=s.size()-1;i>=0;i--){hash+=(s[i]-'a'+1)*p;p*=131;mp[hash]++;} }void get_next(string& s) {nt[0]=-1;int i=0,j=-1;while(i<s.size()){if(j==-1||s[i]==s[j])nt[++i]=++j;elsej=nt[j];} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;i++){cin>>s[i];Hash(s[i]);}LL ans=0;for(int i=1;i<=n;i++){get_next(s[i]);ull hash=0;for(int j=0;j<s[i].size();j++){hash=hash*131+s[i][j]-'a'+1;cnt[j+1]=mp[hash];}for(int j=1;j<=s[i].size();j++)cnt[nt[j]]-=cnt[j];for(int j=1;j<=s[i].size();j++)ans=(ans+1LL*cnt[j]*j%mod*j%mod)%mod;}cout<<ans<<endl;return 0; }

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的牛客多校2 - All with Pairs(字符串哈希+next数组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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