[bzoj4084]:[Sdoi2015]双旋转字符串

[bzoj4084]:[Sdoi2015]双旋转字符串

Description

给定两个字符串集合$ S$ 和 $T$ 。其中 $S$ 中的所有字符串长度都恰好为 $N$ ,而 T 中所有字符串长度都恰好为 $M$ 。

且 $N+M $恰好为偶数。如果记 $S$ 中字符串全体为 $S_1,S_2…S_{TotalS}$ ,而 T 中字符串全体为 $T_1,T_2…T_{TotalT}$ 。现在希望知道有多少$i,j$ ,满足将 $S_i$ 和 $T_j$ 拼接后得到的字符串 $S_i+T_j$ 满足双旋转性。

一个长度为偶数字符串$ W $可以表示成两段长度相同的字符串的拼接,即 $W=U+V$。如果 $V$ 可以通过$U$旋转得到,则称$ W $是满足双旋转性的。

比如说字符串 U=“vijos”可以通过旋转得到“ijosv”,“josvi”,“osvij” 或“svijo”
。那么“vijosjosvi”就是满足双旋转性的字符串。


Hint

$2\leq N \times TotalS + M\times TotalT\leq 4\times 10^6$


Solution

对于字符串$A,B$
我们设$mid = (lenA+lenB)/2$
我们考虑长串,显然长串的右半部分$A_{mid+1}A_{mid+2}..A_{r}$一定是左半部分$A_1A_2..A_{mid}$的子串将左半部分的子串复制一下,扩展成两倍,我们就可以在这个新的串中枚举其右半部分出现的位置,然后把剩下的部分丢到map里。

对于每一个字符串$B$,求出其hash值,然后在map里找即可

复杂度大概是$O(n|S|+m|T|+mlog|S|)$


Code

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef unsigned long long ll;
const int N = 8e6 + 29;
const int base = 233;
int n, m, lenA, lenB, mid, r;
char c[N];
long long ans;
ll h[N], b[N], a[N];
map<ll, int>mmp;

int main() {
    scanf("%d%d%d%d", &n, &m, &lenA, &lenB);
    b[0] = 1;
    for(int i = 1; i <= lenA * 2; ++i)
        b[i] = b[i - 1] * 233;
    mid = (lenA + lenB) >> 1;
    r =  lenA - mid;
    while(n--) {
        scanf("%s", c + 1);
        ll MidString = 0; int cnt = 0;
        for(int i = mid + 1; i <= lenA; ++i)
            MidString = MidString * base + c[i];
        for(int i = 1; i <= mid; ++i)
            c[i + mid] = c[i];
        h[0] = 0;
        for(int i = 1; i <= mid * 2; ++i) 
            h[i] = h[i - 1] * base + c[i];
        for(int i = 1; i <= mid; ++i) {
            ll qwq = h[i + r - 1] - h[i - 1] * b[r];
            if(qwq != MidString) continue;
            a[++cnt] = h[i + mid - 1] - h[i + r - 1] * b[mid - r];
        }
        sort(a + 1, a + 1 + cnt);
        cnt = unique(a + 1, a + 1 + cnt) - a - 1;
        for(int i = 1; i <= cnt; ++i)
            mmp[a[i]]++;
    }
    while(m--) {
        scanf("%s", c + 1);
        ll qwq = 0;
        for(int i = 1; i <= lenB; ++i)
            qwq = qwq * base + c[i];
        ans += mmp[qwq];
    }
    printf("%lld\n", ans);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒