Brief description:

。。。 SPOJ 705. New Distinct Substrings 和 URAL 1297. Palindrome 的结合。。。。
求一个字符串中，回文子串的个数（内容相同，位置不同的算一个）。
。。。时隔这么久，再做一遍依然觉得这是一道不可多得的好题。。。

Analysis:

。。。这个题有两种风格迥异的做法。后缀数组凹和 Hash 乱搞。。。
。。。两种做法都有可取之处、可以互相借鉴。
。。。对于回文子串问题。我们知道经过 Interleave 之后。（$.a.a.a.a. ）。
。。就不需要讨论回文串长度的奇偶了。。（这样得到的答案需要 / 2。。因为每种回文串（包括空串）都会多计数一次。。）
。。下面的做法都默认这一点。。

算法一：后缀数组

我们首先回忆 SPOJ 705. New Distinct Substrings。。。

在这个题中。。我们从左往右扫描每个后缀，并统计所有前缀在 sa[i] 的贡献。
。这个数值是： n-sa[i]-h[i]。只所以要减去 h[i] 是因为这些串之前已经被统计过，避免重复计数。

再回忆 URAL 1297. Palindrome 。。。（仅讨论奇数长度的回文子串）。。。

在那个题中。。我们检查所有所有 lcpp(i, n-1-i) 。。从中选出答案最大的即可。。。
而现在我们需要完成计数。。我们类比前面一个题。。将所有 lcpp(i, n-1-i) 取出。。
。。。形成一个新的 SA。。。在得到 h[]。。我们就可以如法炮制。。
而我们可以很方便的得到新的 SA。。。。

...
int hh[N], oo[N]; bool cp(int a,int b){
    int t = lcpp(a, b);
    if (t <= hh[a]) return t <= hh[b] ? r[a]<r[b] : 0;
    else return t <= hh[b] ? 1 : hh[a]<hh[b];
}
...
REP(i, nn) hh[i] = lcpp(i, n-1-i), oo[i] = i; sort(oo, oo+nn, cp);
...

。。当 t <= hh[a] && t <= hh[b] 时。。我们就可以直接用原 SA 中的 rank 数组完成比较（因为这两个串在t+1位置已经分出胜负）。其他情况类似。。。

http://vjudge.net/vjudge/problem/viewSource.action?id=2707432

//}/* .................................................................................................................................. */

const int N = int(4e5) + 9, Z = 256;

int a[3*N], sa[3*N], r[N], h[N];
int C[N], key[N], t1[N], t2[N]; char s[N], _s[N];
int n, _n;

inline void rs(int *x, int *y, int *sa, int n, int m){
    REP(i, n) key[i] = i[y][x];
    memset(C, 0, sizeof(C[0]) * m);
    REP(i, n) ++C[key[i]];
    FOR(i, 1, m) C[i] += C[i-1];
    DWN(i, n, 0) sa[--C[key[i]]] = y[i];
}

void da(int a[], int sa[], int n, int m){
    int *x = t1, *y = t2;
    memset(C, 0, sizeof(C[0]) * m);
    REP(i, n) ++C[x[i] = a[i]];
    FOR(i, 1, m) C[i] += C[i-1];
    DWN(i, n, 0) sa[--C[x[i]]] = i;
    for (int l = 1, p = 1; p < n; l <<= 1, m = p){
        p = 0; FOR(i, n-l, n) y[p++] = i;
        REP(i, n) if (sa[i] >= l) y[p++] = sa[i] - l;
        rs(x, y, sa, n, m), swap(x, y), x[sa[0]] = 0, p = 0; FOR(i, 1, n)
            x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+l] == y[sa[i-1]+l]) ? p : ++p;
        ++p;
    }
}

#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int *r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
 else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}

void dc3(int a[], int *sa, int n, int m){
    int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)/3, tbc=0, p;
    a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;

    rs(a+2,t1,t2,tbc,m), rs(a+1,t2,t1,tbc,m), rs(a,t1,t2,tbc,m);
    p = 0, an[F(t2[0])] = 0; FOR(i, 1, tbc)
        an[F(t2[i])] = c0(a,t2[i-1],t2[i]) ? p : ++p;

    if (++p < tbc) dc3(an,san,tbc,p);
    else REP(i, tbc) san[an[i]] = i;

    REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;
    if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);
    REP(i, tbc) key[t2[i]=G(san[i])] = i;

    for(i=0,j=0,p=0; i<ta && j<tbc; p++)
        sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];
    for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];
}

void print_sa(){
    REP_1(i, n){
        cout << sa[i] << ": ";
        FOR(j, sa[i], n) putchar(a[j]);
        puts("");
    }
}

int get_h(){
    REP_1(i, n) r[sa[i]] = i;
    int k = 0; for (int i = 0; i < n; h[r[i++]] = k){
        if (k) --k; for (int j = sa[r[i]-1]; a[i+k] == a[j+k]; ++k);
    }
}

const int LV = 21; int ST[LV][N];
#define cmp(a,b)(h[a]<h[b]?a:b)
int lcp(int l, int r){
    int lv = lg2(r-l); ++l,++r;
    return min(h[ST[lv][l]], h[ST[lv][r-_1(lv)]]);
}


int lcpp(int l, int r){
    //if (l == r) return nn-l;
    l = ::r[l], r = ::r[r]; if (l > r) swap(l, r);
    return lcp(l, r);
}
void get_lcp(){
    REP_1(i, n) ST[0][i] = i;
    for (int lv=1;_1(lv)<=n;++lv)
        for (int i=1;i+_1(lv)<=n+1;++i)
            ST[lv][i] = cmp(ST[lv-1][i], ST[lv-1][i+_1(lv-1)]);
}
#undef cmp


int hh[N], oo[N]; bool cp(int a,int b){
    int t = lcpp(a, b);
    if (t <= hh[a]) return t <= hh[b] ? r[a]<r[b] : 0;
    else return t <= hh[b] ? 1 : hh[a]<hh[b];
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{

        RS(_s); int _n = strlen(_s);

        REP(i, _n) s[2*i] = '.', s[2*i+1] = _s[i]; int nn = 2*_n+1; s[nn-1] = '.';
        n = 0; REP(i, nn) a[n++] = s[i]; a[n++] = '$';

        DWN(i, nn, 0) a[n++] = s[i]; a[n] = 0; dc3(a,sa,n+1,Z); get_h(); get_lcp();
		//print_sa();

		REP(i, nn) hh[i] = lcpp(i, n-1-i), oo[i] = i; sort(oo, oo+nn, cp);

        int z = 0, i1; REP(ii, nn){
            int i = oo[ii]; z += hh[i];
            if (ii) z -= min(hh[i], hh[i1], lcpp(i, i1));
            i1 = i;
        }
        OT(z/2);
	}
}

算法二：Manacher + Hash

注意到不同 Palindromes 的总数是 O(n) 的。。所以可以用 Manacher + Hash 暴力。。。方法是枚举每个回文中心，按照回文半径从大到小利用字符串 Hash 枚举回文串，当出现已经出现过的回文串是直接 break; 掉。。（更小的回文串一定也出现过。。）

（。。这种方法还是比较危险。。。最好用一些方法减少冲突的机会。。）
（。奇偶长度分开讨论，不放进相同的 Hash 表里。。）
（。开 uLL。。。）
（。双 hash（多取几个模或者 + 长度信息）。。。）

实际中应该 3 的效果最稳定。。。

http://vjudge.net/vjudge/problem/viewSource.action?id=2706937

External link:

http://hi.baidu.com/lccycc_acm/item/70cf7e3f389ddd5881f1a7d3

Posted by xiaodao
Category: HDU, 日常