C-Seek the Name,Seek the Fame POJ-2752(列挙+hash)

12539 ワード

ぶんせき
題意
  • は私たちにsを与えて、同じ長さの接頭辞と接尾辞のサブ列の長さがどれらがあるかを判断して、小さいから大きいまでこれらの長さ
  • を出力します.
    考え方
  • 前処理文字列のhash値、暴力列挙長は、hash値によって同じ
  • を判読する.
    コード#コード#
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    /* #include  */
    #include 
    void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
    void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
    #define ios ios::sync_with_stdio(false)
    #define Pi acos(-1)
    #define pb push_back
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define db double
    #define Pir pair
    #define m_p make_pair
    #define INF 0x3f3f3f3f
    #define esp 1e-7
    #define mod (ll)(1e9 + 7)
    #define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
    #define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
    #define sc scanf
    #define pr printf
    #define sd(a) scanf("%d", &a)
    #define ss(a) scanf("%s", a)
    using namespace std;
    
    const int mxn = 400005;
    char s[mxn];
    ull hs[mxn];
    ull bse[mxn];
    ull bsc = 31;
    
    void init()
    {
        bse[0] = 1;
        for_(i, 1, mxn - 1)
            bse[i] = bse[i - 1] * bsc;
    }
    
    int main()
    {
        /* fre(); */
        init();
        while(ss(s) != EOF)
        {
            int n = strlen(s);
            hs[n] = 0;
            rep_(i, n - 1, 0)
                hs[i] = hs[i + 1] * bsc + s[i] - 'a';
    
            for_(i, 0, n - 1)
                if(hs[0] - hs[i + 1] * bse[i + 1] == hs[n - i - 1])
                    pr("%d ", i + 1);
            pr("
    "
    ); } return 0; }