4084: [Sdoi2015]雙旋轉字符串

Time Limit:?10 Sec??Memory Limit:?512 MB
Submit:?394??Solved:?161
[Submit][Status][Discuss]

Description

給定兩個字符串集合 S 和 T 。其中 S 中的所有字符串長度都恰好為 N ，而 T 中所有字符串長度都恰好為 M 。且 N+M 恰好為偶數。 如果記 S 中字符串全體為 S1，S2，...，STotalS ,而 T 中字符串全體為 T1，T2，...，TTotalT 。 現在希望知道有多少對 <i,j> ，滿足將 Si 和 Tj 拼接后得到的字符串 Si+Tj 滿足雙旋轉性。 一個長度為偶數字符串 W 可以表示成兩段長度相同的字符串的拼接，即 W=U+V。如果 V 可以通過 U 旋轉得到，則稱 W 是滿足雙旋轉性的。比如說字符串 U=“vijos”可以通過旋轉得到“ijosv”，“josvi”，“osvij” 或“svijo”。那么“vijosjosvi”就是滿足雙旋轉性的字符串。

Input

第一行輸入四個正整數，分別為 TotalS，TotalT，N 和 M，依次表示集合 S 的大小，集合 T 的大小，集合 S 中字符串的長度和集合 T 中字符串的長度。 之后 TotalS 行，依次給出 S 中所有的字符串 Si，1≤i≤TotalS。保證每一個字符串長度都恰為 N ，且字符串只由 26 個小寫字母組成。 之后 TotalT 行，依次給出 T 中所有的字符串 Ti，1≤i≤TotalT。保證每一個字符串長度都恰為 M ，且字符串只由 26 個小寫字母組成。 1≤N≤100；1≤M≤100；1≤TotalS≤100；1≤Total^T≤100,2≤N*TotalS+M*TotalT≤4×10^6，N>=M

Output

輸出一個整數，表示滿足要求的數字對 <i,j> 有多少個。

Sample Input

4 4 7 3
vijosvi
josvivi
vijosos
ijosvsv
jos
vij
ijo
jos

Sample Output

6

HINT

Source

[Submit][Status][Discuss]



一開始題意沒讀好，結果做不出來。。。。

大概是要統計有多少對<i,j>使得串Si + Tj左右兩半循環同構

不妨假設N >= M，反之情況類似

對于T中的每個字符串，先hash一下存在一個桶里面

暴力枚舉S中的每個字符串，假設當前枚舉的是Si

對于這個串，記mid = (N + M) / 2，Si的mid + 1 ~ N位在合并以后顯然是給右邊的半部分用的

可以在1 ~ mid位中暴力查找一下那些位置往后N - mid位與這個短串相等

每次找到一個位置，對于1 ~ mid的剩下的字符，后半部在前前半部放后顯然就確定了Tj

這時候只要在桶里面查詢一下這樣的Tj有多少就行了

記得統計的時候不能重復，就是一類Tj對于每個Si只能用一次

用了雙hash + 離散化處理這個桶，，O(|S| * logM)，復雜度有點感人。。。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std;const int maxn = 4E6 + 4; const int mod1 = 1000000007; const int mod2 = 99999983; typedef long long LL;struct Hash{int h1,h2; Hash(){h1 = h2 = 0;}Hash(int h1,int h2): h1(h1),h2(h2){}Hash operator * (const Hash &B){Hash ret;ret.h1 = 1LL * h1 * B.h1 % mod1;ret.h2 = 1LL * h2 * B.h2 % mod2;return ret;}Hash operator *= (const Hash &B){h1 = 1LL * h1 * B.h1 % mod1;h2 = 1LL * h2 * B.h2 % mod2;}Hash operator += (const int &B){h1 += B; if (h1 >= mod1) h1 -= mod1;h2 += B; if (h2 >= mod2) h2 -= mod2;}Hash operator += (const Hash &B){h1 += B.h1; if (h1 >= mod1) h1 -= mod1;h2 += B.h2; if (h2 >= mod2) h2 -= mod2;}Hash operator -= (const Hash &B){h1 -= B.h1; if (h1 < 0) h1 += mod1;h2 -= B.h2; if (h2 < 0) h2 += mod2;}bool operator < (const Hash &B) const{if (h1 < B.h1) return 1;if (h1 > B.h1) return 0;return h2 < B.h2;}bool operator == (const Hash &B) const {return h1 == B.h1 && h2 == B.h2;}bool operator != (const Hash &B) const {return h1 != B.h1 || h2 != B.h2;} }p;int n,m,ta,tb,mid,cur,Cnt; char ch[maxn];vector <string> A,B; vector <Hash> mi,v,h; vector <int> cnt,vis;Hash GetHash(int L,int R) {Hash ret; if (L > R) return ret;ret = h[R]; if (L > 0) ret -= (h[L - 1] * mi[R - L + 1]);return ret; }void Solve1() {int siz = n - mid; LL Ans = 0; mi.push_back(Hash(1,1));for (int i = 1; i <= n; i++) mi.push_back(mi[i - 1] * p);for (int i = 0; i < tb; i++){string &s = B[i]; Hash now;for (int j = 0; j < m; j++) now *= p,now += s[j];v.push_back(now);}sort(v.begin(),v.end()); cnt.push_back(1);for (int i = 1; i < v.size(); i++)if (v[i] == v[i - 1]) ++cnt[cur];else v[++cur] = v[i],cnt.push_back(1);while (v.size() - 1 > cur) v.pop_back();for (int i = 0; i <= cur; i++) vis.push_back(0);for (int i = 0; i < n; i++) h.push_back(Hash(0,0));for (int i = 0; i < ta; i++){string &s = A[i]; Hash now; ++Cnt;for (int j = 0; j < mid; j++) now *= p,now += s[j],h[j] = now;now = Hash(0,0);for (int j = mid; j < n; j++) now *= p,now += s[j];for (int j = 0; j <= mid - siz; j++){if (GetHash(j,j + siz - 1) != now) continue;Hash Now = GetHash(j + siz,mid - 1);Now *= mi[j]; Now += GetHash(0,j - 1);int pos = lower_bound(v.begin(),v.end(),Now) - v.begin();if (pos < v.size() && v[pos] == Now && vis[pos] != Cnt) Ans += 1LL * cnt[pos],vis[pos] = Cnt;}}cout << Ans << endl; }void Solve2() {int siz = m - mid; LL Ans = 0; mi.push_back(Hash(1,1));for (int i = 1; i <= m; i++) mi.push_back(mi[i - 1] * p);for (int i = 0; i < ta; i++){string &s = A[i]; Hash now;for (int j = 0; j < n; j++) now *= p,now += s[j];v.push_back(now);}sort(v.begin(),v.end()); cnt.push_back(1);for (int i = 1; i < v.size(); i++)if (v[i] == v[i - 1]) ++cnt[cur];else v[++cur] = v[i],cnt.push_back(1);while (v.size() - 1 > cur) v.pop_back();for (int i = 0; i <= cur; i++) vis.push_back(0);for (int i = 0; i < m; i++) h.push_back(Hash(0,0));for (int i = 0; i < tb; i++){string &s = B[i]; Hash now; ++Cnt;for (int j = siz; j < m; j++) now *= p,now += s[j],h[j] = now;now = Hash(0,0);for (int j = 0; j < siz; j++) now *= p,now += s[j];for (int j = siz; j <= m - siz; j++){if (GetHash(j,j + siz - 1) != now) continue;Hash Now = GetHash(j + siz,m - 1);Now *= mi[j - siz]; Now += GetHash(siz,j - 1);int pos = lower_bound(v.begin(),v.end(),Now) - v.begin();if (pos < v.size() && v[pos] == Now && vis[pos] != Cnt) Ans += 1LL * cnt[pos],vis[pos] = Cnt;}}cout << Ans << endl; }int main() {#ifdef DMCfreopen("DMC.txt","r",stdin);#endifp.h1 = 233; p.h2 = 131;cin >> ta >> tb >> n >> m; mid = n + m >> 1;for (int i = 0; i < ta; i++){scanf("%s",ch); string s;for (int j = 0; j < n; j++) s += ch[j];A.push_back(s);}for (int i = 0; i < tb; i++){scanf("%s",ch); string s;for (int j = 0; j < m; j++) s += ch[j];B.push_back(s);}if (n >= m) Solve1(); else Solve2();return 0; }

總結

以上是生活随笔為你收集整理的4084: [Sdoi2015]双旋转字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。