首页 > 代码库 > String Shifting
String Shifting
我们规定对一个字符串的shift操作如下:略去。shift(string, x) = string(0 <= x < n).
分析:一看这题,这不很简单么,直接模拟判断,但是这套路有这么简单么!看数据范围,1e6,那么复杂度就是1e6*1e6=1e12,这样,在1s的时限内,肯定会超时,暴力肯定不行,那就字符串哈希,很早就想写了,但是没有遇到专门的这类题,刚好这道题就练习一下,我忘了那个算法叫什么名字,好像是Rabin-Karp,反正就是对这个字符串算出一个值,然后可以O(1)的转移到下一个字符串,计算出下一个字符串的值,如果这两个值不相等,那么这两个字符串肯定不同,如果相等,那相同的概率就很高,这里需要再次逐个字符判断一下是否相等。这道题,我为了简单起见,就没有再次判断,已经ac。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef unsigned long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 const int key = 131;15 int work(char x) {16 if(x >= ‘A‘ && x <= ‘Z‘)17 return x - ‘A‘;18 return 26 + x - ‘a‘;19 }20 void solve() {21 string s, d;22 cin >> s;23 d = s;24 int res = 1;25 int n = s.size();26 ll t = 0, tag = 1, tar = 0;27 for (int i = 0; i < n; i++) {28 t = t * key + work(s[i]);29 tag *= key;30 }31 tar = t;32 for (int i = 0; i < n - 1; i++) {33 t = t * key - tag * work(s[i]) + work(s[i]);34 if(t == tar) res++;35 }36 cout << res << endl;37 38 }39 int main() {40 freopen("test.in", "r", stdin);41 //freopen("test.out", "w", stdout);42 solve();43 return 0;44 }
String Shifting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。