牛客多校第三场 E Sort String（字符串hash）

89 阅读 0 评论 59 点赞

我是靠谱客的博主舒适外套，最近开发中收集的这篇文章主要介绍牛客多校第三场 E Sort String（字符串hash），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://www.nowcoder.com/acm/contest/141/E
来源：牛客网

题目描述

Eddy likes to play with string which is a sequence of characters. One day, Eddy has played with a string S for a long time and wonders how could make it more enjoyable. Eddy comes up with following procedure:

1. For each i in [0,|S|-1], let Si be the substring of S starting from i-th character to the end followed by the substring of first i characters of S. Index of string starts from 0.
2. Group up all the Si. Si and Sj will be the same group if and only if Si=Sj.
3. For each group, let Lj be the list of index i in non-decreasing order of Si in this group.
4. Sort all the Lj by lexicographical order.

Eddy can't find any efficient way to compute the final result. As one of his best friend, you come to help him compute the answer!

输入描述:

Input contains only one line consisting of a string S.

1≤ |S|≤ 106
S only contains lowercase English letters(i.e. ).

输出描述:

First, output one line containing an integer K indicating the number of lists.
For each following K lines, output each list in lexicographical order.
For each list, output its length followed by the indexes in it separated by a single space.

示例1

输入

复制

abab

输出

复制

2
2 0 2
2 1 3

示例2

输入

复制

deadbeef

输出

复制

题目大意：一开始给出一个字符串S，定义字符串串T[i]=S[i,...,n]+S[1,...,i-1]（i=1,...,n）现在要对这n个字符串进行分类，将所有相同的串放到一个集合，同时对这几个集合按下标的字典序进行排序之后输出。

题目思路：对于这个题，我们可以先将字符串S进行拼接，令SS=S+S，这样每个T[i]=SS[i,...,i+n-1]，然后再借助字符串hash对SS串进行处理，这样就可以在O(1)的时间里求出T[i]的hash值。接着再将hash值相同的串进行分类处理即可。

小小吐槽下，这个题居然卡常数，一开始怕精确度不够用双hash写的，居然T了，后面尝试了下用unsigned long long自然溢出来处理hash值就过了，还是有点小坑的。-，-

具体实现看代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lowbit(x) x&-x
#define MP make_pair
#define pb push_back
#define debug(x) cout<<x<<"= "<<x<<endl;
#define FIN freopen("in.txt","r",stdin);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int MX = 2e6+7;
const int has = 99959;
 

char str[MX];
ull H[MX],P[MX];
unordered_map<ull,int>mp;
void Hash(int n){
    H[0]=P[0]=1;
    for(int i=1;i<=n;i++){
        H[i]=H[i-1]*has+str[i]-'0'+1;
        P[i]=P[i-1]*has;
    }
}
ull get_hash(int l,int r){
    return H[r]-H[l-1]*P[r-l+1];
}
vector<int>ans[MX];

int main(){
    //FIN;
    scanf("%s",str+1);
    int len=strlen(str+1);
    for(int i=len+1;i<=2*len;i++)
        str[i]=str[i-len];
    str[2*len+1]='';
    Hash(2*len);
    int num=0;
    for(int i=1;i<=len;i++){
        ull cnt=get_hash(i,i+len-1);
        if(mp[cnt]==0){
            mp[cnt]=++num;
            ans[num].pb(i-1);
        } else{
            ans[mp[cnt]].pb(i-1);
        }
    }
    printf("%dn",num);
    for(int i=1;i<=num;i++){
        printf("%d ",ans[i].size());
        for(int x:ans[i])
            printf("%d ",x);
        printf("n");
    }
    return 0;
}