UESTC 1703 一道更简单的字符串题 哈希+枚举

一道更简单的字符串题 哈希+枚举

Source

2017 UESTC Training for Search Algorithm & String

UESTC 1703 一道更简单的字符串题

My Solution

求出最小循环串。

哈希+枚举
先把字符串哈希，
然后从ans = 1 ~ n进行枚举，
check的时候枚举每个hash(i, ans) == hash(0, ans),
且对于最后一段长度不到ans的 hash(i, len-i) == hash(0, len-i),
因为是从小到大枚举，所以一旦有ans满足，则就是答案。
这是一个调和级数，故nlin(n)。
时间复杂度 O(nlin(n))
空间复杂度 O(n)

#include 
#include 
#include 
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e6 + 8;
const ull p = 1e12 + 7;             //!

struct HASH{
    ull Hash[MAXN], xp[MAXN];
    void init1(int sz){
        xp[0] = 1;
        for(int i = 1; i <= sz; i++) xp[i] = xp[i-1] * p; } void init2(char *s){//0~n-1 based int sz = strlen(s); Hash[sz] = 0; for(int i = sz - 1; i >= 0; i--){
            Hash[i] = Hash[i+1] * p + (s[i] - 'a' + 1);
        }
    }
    ull get_Hash(const int& st, const int& len){
        return Hash[st] - Hash[st + len] * xp[len];
    }

} hh;

char s[MAXN];
int len;

inline bool check(int x){
    for(int i = x; i < len; i += x){ if(len - i >= x){
            if(hh.get_Hash(i, x) != hh.get_Hash(0, x)){
                return false;
            }
        }
        else{
            if(hh.get_Hash(i, len - i) != hh.get_Hash(0, len - i)){
                return false;
            }
        }

    }
    return true;
}

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    scanf("%s", s);
    len = strlen(s);
    hh.init1(len);
    hh.init2(s);
    int ans = 0, i;
    for(i = 1; i <= len; i++){
        if(check(i)){
            ans = i;
            break;
        }
    }

    printf("%dn", ans);


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx