tokitsukaze
>
2018牛客网暑期ACM多校训练营(第三场)E.Sort String (hash)
转载请注明出处:http://tokitsukaze.live/
题目链接:https://www.nowcoder.com/acm/contest/141/E
题意:
给一个字符串,复制前n-1个字符后,问有多少种长度n的子串,分类后按字典序输出下标。
题解:
复制一遍字符串,然后预处理hash表。之后for每个起始位置,可以在O(1)的时间获取子串的hash值,然后扔进map分类即可。对于这种写法字典序不需要特殊处理。
这个题卡常…有两个点要注意一下。
1.mod取1e9+7会冲突(过了62.5%的数据),而且每次%常数很大,会tle,这里选用了ull(自动%2^64)。
2.要用unordered_map,不然会tle。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| #include <bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define mem(a,b) memset((a),(b),sizeof(a)) #define MP make_pair #define pb push_back #define fi first #define se second #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() using namespace __gnu_cxx; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> PII; typedef pair<ll,ll> PLL; typedef vector<int> VI; typedef vector<ll> VL; const int INF=0x3f3f3f3f; const ll LLINF=0x3f3f3f3f3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-6; const int MAX=2e6+10; const ll mod=1e9+7;
struct hash_table { ull seed; ull Hash[MAX],tmp[MAX]; void set(ull _seed) { seed=_seed; } void work(char *s,int n) { ll i,j; tmp[0]=1; Hash[0]=0; for(i=1;i<=n;i++) tmp[i]=tmp[i-1]*seed; for(i=1;i<=n;i++) Hash[i]=(Hash[i-1]*seed+(s[i]-'a')); } ull get(int l,int r) { return (Hash[r]-Hash[l-1]*tmp[r-l+1]); } }h; char s[MAX]; VI res[MAX]; int main() { int i,j,len,tot; while(~scanf("%s",s+1)) { len=strlen(s+1); for(i=len+1,j=1;j<=len;i++,j++) s[i]=s[j]; for(i=1;i<=len;i++) res[i].clear(); h.set(23333); h.work(s,len*2); unordered_map<ull,int> mp; tot=0; for(i=1;i<=len;i++) { ull tmp=h.get(i,i+len-1); if(!mp.count(tmp)) mp[tmp]=++tot; res[mp[tmp]].pb(i-1); } printf("%d\n",tot); for(i=1;i<=tot;i++) { printf("%d",sz(res[i])); for(auto it:res[i]) printf(" %d",it); puts(""); } } return 0; }
|