首页 > 代码库 > BZOJ1461 字符串的匹配
BZOJ1461 字符串的匹配
什么字符串。。。明明是两个数列。。。
分类上来讲，还是一道很好的noip题。。。（雾）
首先，kmp会不会？（答：会！）
其次，树状数组求顺序对会不会？（再答：会！）
讲完了！>.<
进入正题：
首先，要知道kmp匹配是O(m + n)的原因，是因为匹配每一位的时间是O(1)的。。。
而我们这里是一个数列，每一位需要搞出一个特征值，使得特征值相同 <=> 可以匹配这一位
于是就想到了以这一位为末位的当前已匹配区间内的动态顺序对的数目，而求这个东西是O(n * log n)的
故总复杂度O(m * log m + n * log n)
1 /************************************************************** 2 Problem: 1461 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:644 ms 7 Memory:12564 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 13 #define lowbit(x) x & -x 14 using namespace std; 15 const int S = 10005; 16 const int N = 500005; 17 int a[N], b[N], les[N], equ[N], next[N], ans[N]; 18 int BIT[S]; 19 int n, m, s, tot; 20 21 inline int read(){ 22 int x = 0, sgn = 1; 23 char ch = getchar(); 24 while (ch < ‘0‘ || ch > ‘9‘){ 25 if (ch == ‘-‘) sgn = -1; 26 ch = getchar(); 27 } 28 while (ch >= ‘0‘ && ch <= ‘9‘){ 29 x = x * 10 + ch - ‘0‘; 30 ch = getchar(); 31 } 32 return sgn * x; 33 } 34 35 inline void add(int x, int del){ 36 while (x <= s) 37 BIT[x] += del, x += lowbit(x); 38 } 39 40 inline int query(int x){ 41 int res = 0; 42 while (x) 43 res += BIT[x], x -= lowbit(x); 44 return res; 45 } 46 47 void get_next(){ 48 memset(BIT, 0, sizeof(BIT)); 49 next[1] = 0; 50 int i = 2, j = 0, k; 51 for (; i <= m; ++i){ 52 add(b[i], 1); 53 while (j && (query(b[i] - 1) != les[j + 1] || query(b[i]) != equ[j + 1])){ 54 for (k = i - j; k < i - next[j]; ++k) 55 add(b[k], -1); 56 j = next[j]; 57 } 58 next[i] = ++j; 59 } 60 } 61 62 void kmp(){ 63 memset(BIT, 0, sizeof(BIT)); 64 int i = 1, j = 0, k, res = 0; 65 for (; i <= n; ++i){ 66 add(a[i], 1); 67 while (j && (query(a[i] - 1) != les[j + 1] || query(a[i]) != equ[j + 1])){ 68 for (k = i - j; k < i - next[j]; ++k) 69 add(a[k], -1); 70 j = next[j]; 71 } 72 if (j == m - 1){ 73 ans[++tot] = i - j; 74 for (k = i - j; k < i - next[j]; ++k) 75 add(a[k], -1); 76 j = next[j]; 77 } 78 ++j; 79 } 80 } 81 82 int main(){ 83 int i; 84 n = read(), m = read(), s = read(); 85 for (i = 1; i <= n; ++i) 86 a[i] = read(); 87 for (i = 1; i <= m; ++i) 88 b[i] = read(); 89 memset(BIT, 0, sizeof(BIT)); 90 for (i = 1; i <= m; ++i){ 91 add(b[i], 1); 92 les[i] = query(b[i] - 1); 93 equ[i] = query(b[i]); 94 } 95 get_next(); 96 kmp(); 97 printf("%d\n", tot); 98 for (i = 1; i <= tot; ++i) 99 printf("%d\n", ans[i]);100 return 0;101 }
(p.s. 如有不懂请Orz此巨巨)
BZOJ1461 字符串的匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。