首页 > 代码库 > 【BZOJ4259】 残缺的字符串
【BZOJ4259】 残缺的字符串
Description
很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。
你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?
Input
第一行包含两个正整数m,n(1<=m<=n<=300000)，分别表示A串和B串的长度。
第二行为一个长度为m的字符串A。
第三行为一个长度为n的字符串B。
两个串均仅由小写字母和*号组成，其中*号表示相应位置已经残缺。
Output
第一行包含一个整数k，表示B串中可以完全匹配A串的位置个数。
若k>0，则第二行输出k个正整数，从小到大依次输出每个可以匹配的开头位置（下标从1开始）。
Sample Input
3 7
a*b
aebr*ob
a*b
aebr*ob
Sample Output
2
1 5
1 5
HINT
Source
By Claris
Solution
对于每个字母的权值就设为1~26。*的权值设为0。两个字符可以匹配当且仅当A_i∗B_j∗(A_i−B_j )^2等于0。那么我们将这个式子展开，展开以后的每一项分别用FFT计算即可。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstring> 5 6 #define R register 7 #define maxn 1048576 8 typedef long double db; 9 const db pi = acosl(-1);10 char A[maxn], B[maxn];11 struct Complex {12 db x, y;13 inline Complex operator - (const Complex &that) const {return (Complex) {x - that.x, y - that.y};}14 inline Complex operator * (const Complex &that) const {return (Complex) {x * that.x - y * that.y, x * that.y + y * that.x};}15 inline void operator += (const Complex &that) {x += that.x; y += that.y;}16 } w[maxn];17 int N;18 void init()19 {20 R int h = N >> 1;21 for (R int i = 0; i < h; ++i) w[i + h] = (Complex) {cos(2 * pi / N * i), sin(2 * pi / N * i)};22 for (R int i = h; i--; ) w[i] = w[i << 1];23 }24 void bit_reverse(R Complex *a, R Complex *b)25 {26 for (R int i = 0; i < N; ++i) b[i] = a[i];27 for (R int i = 0, j = 0; i < N; ++i)28 {29 i > j ? std::swap(b[i], b[j]), 1 : 0;30 for (R int l = N >> 1; (j ^= l) < l; l >>= 1);31 }32 }33 void dft(R Complex *a)34 {35 for (R int l = 2, m = 1; m != N; l <<= 1, m <<= 1)36 for (R int i = 0; i < N; i += l)37 for (R int j = 0; j < m; ++j)38 {39 R Complex tmp = a[i + j + m] * w[j + m];40 a[i + j + m] = a[i + j] - tmp;41 a[i + j] += tmp;42 }43 }44 Complex a[maxn], b[maxn], ta[maxn], tb[maxn], tc[maxn], ans[maxn];45 int aa[maxn], bb[maxn];46 int main()47 {48 R int la, lb;49 scanf("%s%s", A, B);50 la = strlen(A); lb = strlen(B);51 for (N = 1; N < (la + lb); N <<= 1);52 init();53 std::reverse(A, A + la);54 for (R int i = 0; i < la; ++i) A[i] == ‘*‘ ? 0 : aa[i] = A[i] - ‘a‘ + 1;55 for (R int i = 0; i < lb; ++i) B[i] == ‘*‘ ? 0 : bb[i] = B[i] - ‘a‘ + 1;56 57 for (R int i = 0; i < la; ++i) a[i].x = aa[i] * aa[i] * aa[i], a[i].y = 0;58 for (R int i = 0; i < lb; ++i) b[i].x = bb[i], b[i].y = 0;59 bit_reverse(a, ta); bit_reverse(b, tb);60 dft(ta); dft(tb);61 for (R int i = 0; i < N; ++i) ans[i] += (ta[i] * tb[i]);62 63 for (R int i = 0; i < la; ++i) a[i].x = -2 * aa[i] * aa[i], a[i].y = 0;64 for (R int i = 0; i < lb; ++i) b[i].x = bb[i] * bb[i], b[i].y = 0;65 bit_reverse(a, ta); bit_reverse(b, tb);66 dft(ta); dft(tb);67 for (R int i = 0; i < N; ++i) ans[i] += (ta[i] * tb[i]);68 69 for (R int i = 0; i < la; ++i) a[i].x = aa[i], a[i].y = 0;70 for (R int i = 0; i < lb; ++i) b[i].x = bb[i] * bb[i] * bb[i], b[i].y = 0;71 bit_reverse(a, ta); bit_reverse(b, tb);72 dft(ta); dft(tb);73 for (R int i = 0; i < N; ++i) ans[i] += (ta[i] * tb[i]);74 75 std::reverse(ans + 1, ans + N);76 bit_reverse(ans, tc);77 dft(tc);78 // for (R int i = 0; i < N; ++i) printf("%lf %lf\n", tc[i].x, tc[i].y);79 for (R int i = la - 1; i < lb; ++i) if (fabs(tc[i].x / N) < 0.5) printf("%d ", i - la + 2);80 return 0;81 }82 /*83 399906 399924 399942 399960 399978 39999684 */
其实这题的数据用bitset是可以水过的。不过可以卡。然后我优化了一发常数就只是最慢的数据本机3s以内了。我把代码放在这里欢迎大家来hack! O(∩_∩)O~~
1 #include <cstdio> 2 #include <cstring> 3 #include <bitset> 4 #include <algorithm> 5 6 #define R register 7 #define maxn 500010 8 #define maxs 15635 9 //#define inline 10 char A[maxn], B[maxn]; 11 /*inline bool eq(R char a, R char b) 12 { 13 return a == b || a == ‘*‘ || b == ‘*‘; 14 }*/ 15 typedef unsigned uint; 16 int len; 17 18 #define set(v, x) (v[x >> 5] |= 1u << (x & 31)) 19 #define query(v, x) ((1u << (x & 31)) & v[x >> 5]) 20 uint p[26][32][maxs]; 21 uint aph[26][maxs], ans[maxs]; 22 inline void init(R int c) 23 { 24 R uint *t = p[c][0], *tt; 25 for (R int i = 0; i <= len; ++i) t[i] = aph[c][i]; 26 for (R int i = 1; i < 32; ++i) 27 { 28 t = p[c][i]; tt = p[c][i - 1]; 29 for (R int j = 0; j <= len; ++j) 30 t[j] = ((tt[j] >> 1) | ((tt[j + 1] & 1u) << 31)); 31 } 32 } 33 int cnt; 34 inline void bit_and(R int c, R int l) 35 { 36 R int fir = l >> 5; R uint *t = p[c][l & 31]; 37 R int i = fir, j = 0; 38 for (; i + 36 < len; i += 36, j += 36) 39 { 40 ans[j] &= t[i]; 41 ans[j + 1] &= t[i + 1]; 42 ans[j + 2] &= t[i + 2]; 43 ans[j + 3] &= t[i + 3]; 44 ans[j + 4] &= t[i + 4]; 45 ans[j + 5] &= t[i + 5]; 46 ans[j + 6] &= t[i + 6]; 47 ans[j + 7] &= t[i + 7]; 48 ans[j + 8] &= t[i + 8]; 49 ans[j + 9] &= t[i + 9]; 50 ans[j + 10] &= t[i + 10]; 51 ans[j + 11] &= t[i + 11]; 52 ans[j + 12] &= t[i + 12]; 53 ans[j + 13] &= t[i + 13]; 54 ans[j + 14] &= t[i + 14]; 55 ans[j + 15] &= t[i + 15]; 56 ans[j + 16] &= t[i + 16]; 57 ans[j + 17] &= t[i + 17]; 58 ans[j + 18] &= t[i + 18]; 59 ans[j + 19] &= t[i + 19]; 60 ans[j + 20] &= t[i + 20]; 61 ans[j + 21] &= t[i + 21]; 62 ans[j + 22] &= t[i + 22]; 63 ans[j + 23] &= t[i + 23]; 64 ans[j + 24] &= t[i + 24]; 65 ans[j + 25] &= t[i + 25]; 66 ans[j + 26] &= t[i + 26]; 67 ans[j + 27] &= t[i + 27]; 68 ans[j + 28] &= t[i + 28]; 69 ans[j + 29] &= t[i + 29]; 70 ans[j + 30] &= t[i + 30]; 71 ans[j + 31] &= t[i + 31]; 72 ans[j + 32] &= t[i + 32]; 73 ans[j + 33] &= t[i + 33]; 74 ans[j + 34] &= t[i + 34]; 75 ans[j + 35] &= t[i + 35]; 76 } 77 for (; i <= len; ++i, ++j) ans[j] &= t[i]; 78 } 79 80 //std::bitset<maxn> aph[26], ans; 81 int fail[maxn]; 82 int r[maxn]; 83 inline bool cmp(R int a, R int b) {return A[a] < A[b] || (A[a] == A[b] && (a & 31) < (b & 31));} 84 int main() 85 { 86 // freopen("str.in", "r", stdin); 87 // freopen("str.out", "w", stdout); 88 scanf("%s%s", A, B); 89 R int la = strlen(A), lb = strlen(B); 90 len = lb >> 5; 91 R int xcnt = 0; 92 for (R int i = 0; i < la; ++i) xcnt += A[i] == ‘*‘; 93 for (R int i = 0; i < lb; ++i) xcnt += B[i] == ‘*‘; 94 /*if (!xcnt) 95 { 96 fail[1] = 0; 97 for (R int i = la; i; --i) A[i] = A[i - 1]; 98 for (R int i = lb; i; --i) B[i] = B[i - 1]; 99 for (R int i = 2, p = 0; i <= la; ++i)100 {101 while (p && A[p + 1] != A[i]) p = fail[p];102 A[p + 1] == A[i] ? ++p : 0;103 fail[i] = p;104 }105 for (R int i = 1, p = 0; i <= lb; ++i)106 {107 while (p && A[p + 1] != B[i]) p = fail[p];108 A[p + 1] == B[i] ? ++p : 0;109 if (p == la)110 {111 printf("%d ", i - la + 1);112 p = fail[p];113 }114 }115 puts("");116 return 0;117 }*/118 for (R int i = 0; i < lb; ++i)119 {120 if (B[i] != ‘*‘) set(aph[B[i] - ‘a‘], i);121 else for (R int j = 0; j < 26; ++j) set(aph[j], i);122 set(ans, i);123 }124 for (R int i = 0; i < 26; ++i) init(i);125 // fprintf(stderr, "%d %d\n", ‘*‘, ‘a‘);126 for (R int i = 0; i < la; ++i) r[i] = i;127 std::sort(r, r + la, cmp);128 for (R int i = 0; i < la; ++i)129 if (A[r[i]] != ‘*‘)130 bit_and(A[r[i]] - ‘a‘, r[i]);131 // ans &= (aph[A[i] - ‘a‘] >> i);132 for (R int i = 0; i + la - 1 < lb; ++i) if (query(ans, i)) printf("%d ", i + 1); puts("");133 return 0;134 }
【BZOJ4259】 残缺的字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。