E-Sort String 字符串hash+hash表做法
这题一开始就想到了要O(1)得到起始点为i(0~len-1)长度为len的每一个串的hash值，但是在这之后如果不能O(n)的在容器里将他们分类排序的话基本上就超时(sort排序超了凉凉);
用字符串hash将翻倍了的字符串hash一遍，然后O1得到每一个len长的串的hash值，将每一个很大的hash值用hash表存起来分配到vector里输出；
这题用了双hash，hash值里用到的INF如果是1e9的话还是有可能hash冲突的（就比如说我这个非洲人就wa了，别人交就过了。）
///耗时:817ms(菜鸡的代码，写的很挫) 内存使用:152288kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+1e5+7, w=26;
const ll INF=2e9;///这个值为1e9可能还会有冲突
void write(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
int len, cnt;
struct has
{
ll P;
ll mi_w[maxn];
ll hs[maxn];
void init(char *s)
{
P=1e9+rand();
mi_w[0]=1;
for(int i=1; i<=len; i++)
mi_w[i]=mi_w[i-1]*w%P;
for(int i=1; i<=len; i++)
hs[i]=(hs[i-1]*w+s[i]-'0')%P;
}
ll get(int l,int r)
{
return ((hs[r]-hs[l-1]*mi_w[r-l+1])%P+P)%P;
}
bool ok(int l,int r)
{
return (get(1,l)+get(l+1,r)-get(r+1,len))%P==0;
}
}h[2];
const int Size=2333237;///hash表用的mod
struct Hash{
int num[Size];
ll key[Size];
void init(){
memset(num, 0, sizeof(num));
memset(key, -1, sizeof(key));
}
int Insert(ll x){
int num1=x%Size;
while(key[num1]!=-1){
if(key[num1]==x){
return num[num1];
}
++num1;
if(num1>=Size)
num1-=Size;
}
key[num1]=x;
num[num1]=cnt++;
return num[num1];
}
}th;
char str[maxn];
vector<int> vv[maxn/2];
int main(){
register int j, i, slen, top, sav;
register ll aaa;
srand(time(0));
scanf("%s", str+1);
len=slen=strlen(str+1);
th.init();
len*=2;
for(i=1;i<=slen;++i)///翻倍
str[i+slen]=str[i];
h[0].init(str);
h[1].init(str);
cnt=0;
for(i=1; i<=slen; ++i){
aaa=h[0].get(i, i+slen)*INF+h[1].get(i, i+slen);
sav=th.Insert(aaa);///插入的时候如果插入过这个数字就返回保存的下标值，没插入过就返回新保存的下标值
vv[sav].push_back(i-1);
}
write(cnt);
putchar('\n');
for(i=0; i<cnt; ++i){
sav=vv[i].size();
write(sav);
for(j=0; j<sav; ++j)
putchar(' '), write(vv[i][j]);
putchar('\n');
}
}
用next数组找循环节的方法刚刚补了一下，果然快了好多;
耗时:138ms 内存使用:14056kb
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+7;
int Next[N];
void write(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
void getNext(char *s, int &len){
Next[0]=-1;
register int i=0,k=-1;
while(i<len){
if(k==-1||s[i]==s[k]){
Next[++i]=++k;
}
else{
k=Next[k];
}
}
}
char str[N];
int main(){
register int i, j, len, cnt;
scanf("%s", &str);
len=strlen(str);
getNext(str, len);
if(len%(len-Next[len])==0&&Next[len]){
cnt=len-Next[len];
write(len-Next[len]);
putchar('\n');
for(i=0; i<cnt; ++i){
write(len/(len-Next[len]));
for(j=i; j<len; j+=cnt){
putchar(' ');
write(j);
}
putchar('\n');
}
}else{
write(len);
putchar('\n');
for(i=0; i<len; ++i){
putchar('1');
putchar(' ');
write(i);
putchar('\n');
}
}
}
