E-Sort String

kmp next数组的应用

这题很常见题型， 类似于HDU3746。
通过next数组找到最小循环节， 如果 len % (len - next[len]) == 0 说明都是由最小循环节构成的。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+10;
char str[maxn];
int nex[maxn];

void getNext(int tlen) {
    int j = 0, k = -1;
    nex[0] = -1;
    while (j < tlen) {
        if (k == -1 || str[j] == str[k]) {
            nex[++j] = ++k;
        } else {
            k = nex[k];
        }
    }
}


int main(void) {
    cin >> str;
    int len = strlen(str);
    getNext(len);
    int x = len - nex[len];
    if (len % x != 0) {
        cout << len << '\n';
        for(int i = 0; i < len; i++) {
            cout << 1 << ' ' << i << '\n';
        }
    }
    else {
        cout << x << '\n';
        for(int i = 0; i < x; i++) {
            cout << len / x;
            for(int j = i; j < len; j += x)
                cout << ' ' << j;
            puts("");
        }
    }
    return 0;
}