|
Posted on 2011-05-10 15:24 Uriel 阅读(628) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 字符串处理
最近一直在准备省赛,基本都是复习算法和组队赛,基本没切什么题. 昨天想省赛前POJ刷到1200先,就跟光光对拍了下POJ过的题. 发现了这道字符串,顺便复习下KMP和后缀数组啥的. 这题跟POJ 3080基本完全一样,当年写过个解题报告 http://www.cppblog.com/Uriel/articles/98530.html 那时候还不会后缀数组,就用KMP和strstr两种方法水过去了. POJ 3450这题大概数据也不是很强吧...用KMP和strstr也都可以过的. 今天又试了下后缀数组,速度好慢... = = 后缀数组代码参考了 http://www.cnblogs.com/ltang/archive/2010/11/30/1891708.html 发现罗穗骞论文的代码里calheight那个函数数组下标那里可能会越界...,还请路过的大牛们指教.现在是照着上面那个Blog里的代码改了
各算法运行时间如下: KMP: C++ 1469Ms strstr: C++ 969Ms
Suffix Array (DA): C++ 1063Ms G++ 875Ms Suffix Array (DC3): C++ 1063Ms
各算法的代码如下:
KMP
/**//* * Problem: 3450 User: Uriel * Memory: 8424K Time: 1469MS * Language: C++ Result: Accepted */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm>
using namespace std;
int start, n, nxt[210]; char str[40010][210];
struct P { char res[210]; } Ans[4100];
char dest[100];
bool cmp(P a, P b) { return strcmp(a.res, b.res) < 0; }
void GetNext(char* str) { nxt[0] = -1; int i = 0, j = -1; while (str[i]) { if (j == -1 || str[i] == str[j]) { i++; j++; nxt[i] = j; } else j = nxt[j]; } }
int kmpMatch(char* Src, char* Dest) { int i = 0, j = 0, s_len, p_len, sum = 0; s_len = strlen(Src); p_len = strlen(Dest); M: while (i < s_len && j < p_len) { if (j == -1 || Src[i] == Dest[j]) { if (j == p_len - 1) return i - p_len + 1; i++; j++; } else j = nxt[j]; } return -1; }
void Sov() { int i; for (i = 1; i < n; i++) { if (kmpMatch(str[i], dest) == -1) { start = 1; return; } } return; }
int main() { int i, j, k, s, len; while (scanf("%d", &n), n) { scanf("%d", &n); memset(str, 0x00, sizeof(str)); for (i = 0; i < n; i++) scanf("%s", str[i]); len = strlen(str[0]); s = 0; for (i = len; i >= 1; i--) { j = 0; while (j + i <= len) { start = 0; memset(dest, 0x00, sizeof(dest)); strncpy(dest, &str[0][j], i); GetNext(dest); Sov(); if (!start) { strcpy(Ans[s++].res, dest); } j++; } if (s) break; } if (s) { sort(Ans, Ans + s, cmp); printf("%s\n", Ans[0].res); } else { puts("IDENTITY LOST"); } } return 0; }
strstr
/**//* * Problem: 3450 User: Uriel * Memory: 8424K Time: 969MS * Language: C++ Result: Accepted */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm>
using namespace std;
int start, n; char str[40010][210];
struct P { char res[210]; } Ans[4100];
char dest[100]; int Next[100];
bool cmp(P a, P b) { return strcmp(a.res, b.res) < 0; }
void Sov() { int i; for (i = 1; i < n; i++) { if (strstr(str[i], dest) == NULL) { start = 1; return; } } return; }
int main() { int i, j, k, s, len; while (scanf("%d", &n), n) { scanf("%d", &n); memset(str, 0x00, sizeof(str)); for (i = 0; i < n; i++) scanf("%s", str[i]); len = strlen(str[0]); s = 0; for (i = len; i >= 1; i--) { j = 0; while (j + i <= len) { start = 0; memset(dest, 0x00, sizeof(dest)); strncpy(dest, &str[0][j], i); Sov(); if (!start) { strcpy(Ans[s++].res, dest); } j++; } if (s) break; } if (s) { sort(Ans, Ans + s, cmp); printf("%s\n", Ans[0].res); } else { puts("IDENTITY LOST"); } } return 0; }
Suffix Array (DA)
/**//* * Problem: 3450 User: Uriel * Memory: 3604K Time: 875MS * Language: G++ Result: Accepted */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1000000 int n, r[N], sa[N]; int wa[N], wb[N], wv[N], ws[N];
int cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a + l] == r[b + l]; } void da(int *r, int *sa, int n, int m) { int i, j, p, *x = wa, *y = wb, *t; for (i = 0; i < m; i++) ws[i] = 0; for (i = 0; i < n; i++) ws[x[i] = r[i]]++; for (i = 1; i < m; i++) ws[i] += ws[i - 1]; for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i; for (j = 1, p = 1; p < n; j *= 2, m = p) { for (p = 0, i = n - j; i < n; i++) y[p++] = i; for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j; for (i = 0; i < n; i++) wv[i] = x[y[i]]; for (i = 0; i < m; i++) ws[i] = 0; for (i = 0; i < n; i++) ws[wv[i]]++; for (i = 1; i < m; i++) ws[i] += ws[i - 1]; for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i]; for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; } return; } int rank[N], height[N]; void calheight(int *r) { int i, j, k; for (i = 0; i < n; i++) rank[sa[i]] = i; for (i = 0, height[0] = k = 0; i < n; height[rank[i++]] = k) for (k ? k-- : 0, j = (rank[i] > 0) ? sa[rank[i] - 1] : 0; rank[i] > 0 && r[i + k] == r[j + k]; k++) ; }
int main() { int m, t, i, j, sp, sb, se, mid, s, l, ans, c, w, ll; char str[210]; bool visit[4010], isfind; while (scanf("%d", &m), m) { sp = 27; for (j = n = 0; j < m; j++) { scanf("%s", str); for (i = 0; str[i]; i++) { r[n++] = str[i] - 'a'; } r[n++] = sp++; } ll = strlen(str); da(r, sa, n, sp), calheight(r); for (sb = 1, se = ll, mid = (sb + se) >> 1, s = 0, ans = -1; sb < se;) { isfind = false; for (int i = 0; (i < n) && !isfind; i++) { if (height[i] < mid) memset(visit, false, sizeof(visit)), t = 0; if (height[i] >= mid) { if (t == 0) { l = sa[i - 1] / (ll + 1); if (!visit[l]) visit[l] = true, t++; } l = sa[i] / (ll + 1); if (!visit[l]) visit[l] = true, t++; if (t == m) isfind = true, ans = i; } } if (isfind && mid == se) break; if (isfind) (sb == mid && se > sb) ? (mid = se) : (sb = mid); else se = mid - 1, mid = (se + sb) >> 1; } if (ans != -1) { for (int i = 0; i < mid; i++) { c = r[sa[ans] + i]; putchar(c + 'a'); } puts(""); } else puts("IDENTITY LOST"); } return 0; }
Suffix Array (DC3)
/**//* * Problem: 3450 User: Uriel * Memory: 4084K Time: 1110MS * Language: C++ Result: Accepted */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1000000 #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) int n, r[N * 3], sa[N * 3]; //注意数组大小 int wa[N], wb[N], wv[N], ws[N];
int c0(int *r, int a, int b) { return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2]; } int c12(int k, int *r, int a, int b) { if (k == 2) return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1); else return r[a] < r[b] || r[a] == r[b] && wv[a + 1] < wv[b + 1]; } void sort(int *r, int *a, int *b, int n, int m) { int i; for (i = 0; i < n; ++i) wv[i] = r[a[i]]; for (i = 0; i < m; ++i) ws[i] = 0; for (i = 0; i < n; ++i) ++ws[wv[i]]; for (i = 1; i < m; ++i) ws[i] += ws[i - 1]; for (i = n - 1; i >= 0; --i) b[--ws[wv[i]]] = a[i]; return; } void dc3(int *r, int *sa, int n, int m) { int i, j, *rn = r + n, *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p; r[n] = r[n + 1] = 0; for (i = 0; i < n; ++i) if (i % 3) wa[tbc++] = i; sort(r + 2, wa, wb, tbc, m); sort(r + 1, wb, wa, tbc, m); sort(r, wa, wb, tbc, m); for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; ++i) rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++; if (p < tbc) dc3(rn, san, tbc, p); else for (i = 0; i < tbc; ++i) san[rn[i]] = i; for (i = 0; i < tbc; ++i) if (san[i] < tb) wb[ta++] = san[i] * 3; if (n % 3 == 1) wb[ta++] = n - 1; sort(r, wb, wa, ta, m); for (i = 0; i < tbc; ++i) wv[wb[i] = G(san[i])] = i; for (i = 0, j = 0, p = 0; i < ta && j < tbc; ++p) sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++]; for (; i < ta; ++p) sa[p] = wa[i++]; for (; j < tbc; ++p) sa[p] = wb[j++]; return; } int rank[N], height[N]; void calheight(int *r) { int i, j, k; for (i = 0; i < n; i++) rank[sa[i]] = i; for (i = 0, height[0] = k = 0; i < n; height[rank[i++]] = k) for (k ? k-- : 0, j = (rank[i] > 0) ? sa[rank[i] - 1] : 0; rank[i] > 0 && r[i + k] == r[j + k]; k++) ; }
int main() { int m, t, i, j, sp, sb, se, mid, s, l, ans, c, w, ll; char str[210]; bool visit[4010], isfind; while (scanf("%d", &m), m) { sp = 27; for (j = n = 0; j < m; j++) { scanf("%s", str); for (i = 0; str[i]; i++) { r[n++] = str[i] - 'a'; } r[n++] = sp++; } ll = strlen(str); dc3(r, sa, n, sp), calheight(r); for (sb = 1, se = ll, mid = (sb + se) >> 1, s = 0, ans = -1; sb < se;) { isfind = false; for (int i = 0; (i < n) && !isfind; i++) { if (height[i] < mid) memset(visit, false, sizeof(visit)), t = 0; if (height[i] >= mid) { if (t == 0) { l = sa[i - 1] / (ll + 1); if (!visit[l]) visit[l] = true, t++; } l = sa[i] / (ll + 1); if (!visit[l]) visit[l] = true, t++; if (t == m) isfind = true, ans = i; } } if (isfind && mid == se) break; if (isfind) (sb == mid && se > sb) ? (mid = se) : (sb = mid); else se = mid - 1, mid = (se + sb) >> 1; } if (ans != -1) { for (int i = 0; i < mid; i++) { c = r[sa[ans] + i]; putchar(c + 'a'); } puts(""); } else puts("IDENTITY LOST"); } return 0; }
|