首页 > 代码库 > UVALive - 4513 Stammering Aliens ——（hash+二分 || 后缀数组加二分）
UVALive - 4513 Stammering Aliens ——（hash+二分 || 后缀数组加二分）
题意：找一个出现了m次的最长子串，以及这时的最右的位置。
hash的话代码还是比较好写的，，但是时间比SA多很多。。
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 40000 + 100; 6 typedef long long ll; 7 const int X = 257; 8 const int mod = (int)1e9 + 7; 9 10 char s[N]; 11 int m,len,pw[N]; 12 int H[N],pos; 13 14 struct node 15 { 16 int id,hash; 17 bool operator < (const node & temp) const 18 { 19 return hash == temp.hash ? id < temp.id : hash < temp.hash; 20 } 21 }p[N]; 22 23 bool solve(int L) 24 { 25 int cnt = 0; 26 pos = -1; 27 for(int i=1;i+L-1<=len;i++) 28 { 29 int id = i; 30 int hash = ((ll)H[i] - (ll)H[i+L]*pw[L]) % mod; 31 if(hash < 0) hash += mod; // 注意这里！ 32 p[i] = (node){id, hash}; 33 } 34 sort(p+1, p+1+ len - L + 1); 35 36 for(int i=1;i<=len-L+1;i++) 37 { 38 if(i == 1 || p[i].hash != p[i-1].hash) cnt = 0; 39 if(++cnt >= m) pos = max(pos, p[i].id); 40 } 41 return pos != -1; 42 } 43 44 int main() 45 { 46 pw[0] = 1; 47 for(int i=1;i<N;i++) pw[i] = 1LL*pw[i-1] * X % mod; 48 while(scanf("%d",&m) == 1 && m) 49 { 50 scanf("%s",s+1); 51 len = strlen(s+1); 52 for(int i=len;i>=1;i--) H[i] = (1LL*H[i+1] * X + s[i] - ‘a‘) % mod; 53 int l = 1, r = len, ans = -1; 54 while(l <= r) 55 { 56 int mid = l + r >> 1; 57 if(solve(mid)) ans = mid, l = mid + 1; 58 else r = mid - 1; 59 } 60 solve(ans); 61 if(ans != -1) printf("%d %d\n",ans, pos-1); 62 else puts("none"); 63 } 64 return 0; 65 }
SA的话，写法需要细细体会一下了。。时间减少了很多。
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 40000 + 100; 6 typedef long long ll; 7 const int X = 257; 8 const int mod = (int)1e9 + 7; 9 10 char s[N]; 11 int m,len,pw[N]; 12 int H[N],pos; 13 14 struct node 15 { 16 int id,hash; 17 bool operator < (const node & temp) const 18 { 19 return hash == temp.hash ? id < temp.id : hash < temp.hash; 20 } 21 }p[N]; 22 23 bool solve(int L) 24 { 25 int cnt = 0; 26 pos = -1; 27 for(int i=1;i+L-1<=len;i++) 28 { 29 int id = i; 30 int hash = ((ll)H[i] - (ll)H[i+L]*pw[L]) % mod; 31 if(hash < 0) hash += mod; // 注意这里！ 32 p[i] = (node){id, hash}; 33 } 34 sort(p+1, p+1+ len - L + 1); 35 36 for(int i=1;i<=len-L+1;i++) 37 { 38 if(i == 1 || p[i].hash != p[i-1].hash) cnt = 0; 39 if(++cnt >= m) pos = max(pos, p[i].id); 40 } 41 return pos != -1; 42 } 43 44 int main() 45 { 46 pw[0] = 1; 47 for(int i=1;i<N;i++) pw[i] = 1LL*pw[i-1] * X % mod; 48 while(scanf("%d",&m) == 1 && m) 49 { 50 scanf("%s",s+1); 51 len = strlen(s+1); 52 for(int i=len;i>=1;i--) H[i] = (1LL*H[i+1] * X + s[i] - ‘a‘) % mod; 53 int l = 1, r = len, ans = -1; 54 while(l <= r) 55 { 56 int mid = l + r >> 1; 57 if(solve(mid)) ans = mid, l = mid + 1; 58 else r = mid - 1; 59 } 60 solve(ans); 61 if(ans != -1) printf("%d %d\n",ans, pos-1); 62 else puts("none"); 63 } 64 return 0; 65 }
顺便想说一下的是，这里不知为何下标从1开始无限WA，以后用SA还是下标从0开始好了。。毕竟不懂SA的具体原理。
UVALive - 4513 Stammering Aliens ——（hash+二分 || 后缀数组加二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。