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。

代码：

#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;
}