一只只会后缀自动机却不会后缀数组的弱鸡做了一下HDU - 1403,结果SAM被卡内存了，然后学习了一下SA。
以下两道题都是求LCS，区别在于字符串长度。
参考blog：https://www.cnblogs.com/victorique/p/8480093.html
HDU - 1403
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #define rank Rank 6 using namespace std; 7 const int MAXN = 2e5+10; 8 char str[MAXN]; 9 int SA[MAXN], rank[MAXN], height[MAXN], sum[MAXN], tp[MAXN]; 10 //rank[i] 第i个后缀的排名, SA[i] 排名为i的后缀的位置, Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP 11 //sum[i] 基数排序辅助数组, 存储小于i的元素有多少个, tp[i] rank的辅助数组(按第二关键字排序的结果),与SA意义一样 12 bool cmp(int *f, int x, int y, int w){return f[x] == f[y] && f[x + w] == f[y + w];} 13 14 void get_SA(char *s, int n, int m) 15 { 16 for(int i = 0; i < m; i++) sum[i] = 0; 17 for(int i = 0; i < n; i++) sum[rank[i] = s[i]]++; 18 for(int i = 1; i < m; i++) sum[i] += sum[i - 1]; 19 for(int i = n - 1; i >= 0; i--) SA[--sum[rank[i]]] = i; 20 for(int len = 1; len <= n; len <<= 1) 21 { 22 int p = 0; 23 for(int i = n - len; i < n; i++) tp[p++] = i; 24 for(int i = 0; i < n; i++) 25 if(SA[i] >= len) 26 tp[p++] = SA[i] - len; 27 for(int i = 0; i < m; i++) sum[i] = 0; 28 for(int i = 0; i < n; i++) sum[rank[tp[i]]]++; 29 for(int i = 1; i < m; i++) sum[i] += sum[i - 1]; 30 for(int i = n - 1; i >= 0; i--) SA[--sum[rank[tp[i]]]] = tp[i]; 31 swap(rank, tp); 32 p = 1; 33 rank[SA[0]] = 0; 34 for(int i = 1; i < n; i++) 35 rank[SA[i]] = cmp(tp, SA[i - 1], SA[i], len) ? p - 1 : p++; 36 if(p >= n) break; 37 m = p; 38 } 39 int k = 0; 40 n--; 41 for(int i = 0; i <= n; i++) rank[SA[i]] = i; 42 for(int i = 0; i < n; i++) 43 { 44 if(k) k--; 45 int j = SA[rank[i] - 1]; 46 while(s[i + k] == s[j + k]) k++; 47 height[rank[i]] = k; 48 } 49 } 50 int main() 51 { 52 while(~scanf("%s", str)) 53 { 54 int len = strlen(str); 55 str[len] = '0'; 56 scanf("%s", str + len + 1); 57 int n = strlen(str); 58 str[n] = 0; //末尾添加一个0 59 get_SA(str, n + 1, 'z' + 1); 60 int sol = 0; 61 for(int i = 1; i < n; i++) 62 { 63 if(SA[i] > len && SA[i - 1] < len) sol = max(sol, height[i]); 64 if(SA[i] < len && SA[i - 1] > len) sol = max(sol, height[i]); 65 } 66 printf("%dn", sol); 67 } 68 return 0; 69 }
SPOJ - LCS
SA版本：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #define rank Rank 6 using namespace std; 7 const int MAXN = 5e5+10; 8 char str[MAXN]; 9 int SA[MAXN], rank[MAXN], height[MAXN], sum[MAXN], tp[MAXN]; 10 //rank[i] 第i个后缀的排名, SA[i] 排名为i的后缀的位置, Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP 11 //sum[i] 基数排序辅助数组, 存储小于i的元素有多少个, tp[i] rank的辅助数组(按第二关键字排序的结果),与SA意义一样 12 bool cmp(int *f, int x, int y, int w){return f[x] == f[y] && f[x + w] == f[y + w];} 13 14 void get_SA(char *s, int n, int m) 15 { 16 for(int i = 0; i < m; i++) sum[i] = 0; 17 for(int i = 0; i < n; i++) sum[rank[i] = s[i]]++; 18 for(int i = 1; i < m; i++) sum[i] += sum[i - 1]; 19 for(int i = n - 1; i >= 0; i--) SA[--sum[rank[i]]] = i; 20 for(int len = 1; len <= n; len <<= 1) 21 { 22 int p = 0; 23 for(int i = n - len; i < n; i++) tp[p++] = i; 24 for(int i = 0; i < n; i++) 25 if(SA[i] >= len) 26 tp[p++] = SA[i] - len; 27 for(int i = 0; i < m; i++) sum[i] = 0; 28 for(int i = 0; i < n; i++) sum[rank[tp[i]]]++; 29 for(int i = 1; i < m; i++) sum[i] += sum[i - 1]; 30 for(int i = n - 1; i >= 0; i--) SA[--sum[rank[tp[i]]]] = tp[i]; 31 swap(rank, tp); 32 p = 1; 33 rank[SA[0]] = 0; 34 for(int i = 1; i < n; i++) 35 rank[SA[i]] = cmp(tp, SA[i - 1], SA[i], len) ? p - 1 : p++; 36 if(p >= n) break; 37 m = p; 38 } 39 int k = 0; 40 n--; 41 for(int i = 0; i <= n; i++) rank[SA[i]] = i; 42 for(int i = 0; i < n; i++) 43 { 44 if(k) k--; 45 int j = SA[rank[i] - 1]; 46 while(s[i + k] == s[j + k]) k++; 47 height[rank[i]] = k; 48 } 49 } 50 int main() 51 { 52 while(~scanf("%s", str)) 53 { 54 int len = strlen(str); 55 str[len] = '0'; 56 scanf("%s", str + len + 1); 57 int n = strlen(str); 58 str[n] = 0; //末尾添加一个0 59 get_SA(str, n + 1, 'z' + 1); 60 int sol = 0; 61 for(int i = 1; i < n; i++) 62 { 63 if(SA[i] > len && SA[i - 1] < len) sol = max(sol, height[i]); 64 if(SA[i] < len && SA[i - 1] > len) sol = max(sol, height[i]); 65 } 66 printf("%dn", sol); 67 } 68 return 0; 69 }
SAM版本：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int kind=26; 4 const int maxn=250000; 5 struct state 6 { 7 state *Next[kind],*link; 8 int len; 9 state() 10 { 11 link=0; 12 len=0; 13 memset(Next,0,sizeof(Next)); 14 } 15 }; 16 int sz; 17 state st[maxn*2+5]; 18 inline state* newnode(int len = 0) 19 { 20 memset(st[sz].Next,0,sizeof(st[sz].Next)); 21 st[sz].link=0; 22 st[sz].len=len; 23 return &st[sz++]; 24 } 25 state *root,*last; 26 void extend(int w) 27 { 28 state* p=last; 29 state* cur=newnode(p->len+1); 30 while(p&&p->Next[w]==0) 31 { 32 p->Next[w]=cur; 33 p=p->link; 34 } 35 if(p) 36 { 37 state* q=p->Next[w]; 38 if(p->len+1==q->len) 39 cur->link=q; 40 else 41 { 42 state* clone=newnode(p->len+1); 43 memcpy(clone->Next,q->Next,sizeof(q->Next)); 44 clone->link=q->link; 45 q->link=clone; 46 cur->link=clone; 47 while(p&&p->Next[w]==q) 48 { 49 p->Next[w]=clone; 50 p=p->link; 51 } 52 } 53 } 54 else cur->link=root; 55 last=cur; 56 } 57 string keyword; 58 int main() 59 { 60 ios::sync_with_stdio(false); 61 while(cin>>keyword) 62 { 63 sz=0; 64 int ans=0; 65 root=newnode(); 66 last=root; 67 for(int i=0;i<keyword.size();i++) 68 extend(keyword[i]-'a'); 69 cin>>keyword; 70 state *p=root; 71 int tmp=0; 72 for(int i=0;i<keyword.size();i++) 73 { 74 if(p->Next[keyword[i]-'a']) 75 { 76 tmp++; 77 p=p->Next[keyword[i]-'a']; 78 } 79 else 80 { 81 82 while(p&&!p->Next[keyword[i]-'a']) 83 p=p->link; 84 if(!p) 85 p=root; 86 if(p->Next[keyword[i]-'a']) 87 { 88 tmp=p->len+1; 89 p=p->Next[keyword[i]-'a']; 90 } 91 else 92 tmp=0; 93 } 94 ans=max(ans,tmp); 95 } 96 cout<<ans<<endl; 97 } 98 return 0; 99 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
