转载请注明出处: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;
/********************************* head *********************************/
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;
}