牛客网暑期ACM多校训练营（第三场）E Sort String【字符串hash】

E Sort String：
常数卡到爆。。。前向星写到爆就是比不过vector。。。
hash过后，直接模拟就行，正解好像是KMP，总之卡到爆。。。

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 2e6 + 10;
ull base = 213;
ull has[MAXN], a[MAXN];
char str[MAXN];
int len, T, cnt = 0;

vector<int> G[MAXN];
unordered_map<ull , int> mp;

inline void init() {
    a[0] = 1, has[0] = 1;
    for(int i = 1; i < MAXN; ++i) a[i] = a[i - 1] * base;
    int res = 0;
    for(int i = 1; i < len + len; ++i) {
        has[i] = has[i - 1] * base + str[i];
        if(i >= len) {
            ull tot = has[i] - has[i - len] * a[len];
            if(!mp[tot]) mp[tot] = ++res;
            G[mp[tot]].push_back(i - len);
        }
    }
    printf("%dn", res);
    for(int i = 1; i <= res; ++i) {
        int lenth = G[i].size();
        printf("%d", lenth);
        for(int j = 0; j < lenth; ++j) {
            printf(" %d", G[i][j]);
        }
        printf("n");
    }
}

int main() {
    scanf("%s", str + 1);
    len = strlen(str + 1);
    for(int i = len + 1; i <= len + len; ++i) str[i] = str[i - len];
    init();
    return 0;
}

最后

以上就是简单银耳汤最近收集整理的关于牛客网暑期ACM多校训练营（第三场）E Sort String【字符串hash】的全部内容，更多相关牛客网暑期ACM多校训练营（第三场）E内容请搜索靠谱客的其他文章。