http://acm.hdu.edu.cn/showproblem.php?pid=1403

将两个串拼接起来,中间加一个'$'就可以用LCP了。

/*78ms,5100KB*/

const int mx = 200005;

char s[mx], s2[100005];
int sa[mx], rk[mx], h[mx], n; /// n=strlen(s)
int t[mx], t2[mx], c[mx]; /// 辅助数组

/// m为最大字符值+1,一般为127,仅小写时123('z'+1),仅大写时91('Z'+1)
/// 调用前先设置好n
void build_sa(int m)
{
    int i, *x = t, *y = t2;
    For(i, m) c[i] = 0;
    For(i, n) c[x[i] = s[i]]++;
    Forr(i, 1, m) c[i] += c[i - 1];
    rFor(i, n - 1) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int p = 0;
        Forr(i, n - k, n) y[p++] = i;
        For(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        For(i, m) c[i] = 0;
        For(i, n) c[x[y[i]]]++;
        Forr(i, 1, m) c[i] += c[i - 1];
        rFor(i, n - 1) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        Forr(i, 1, n) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++);
        if (p >= n) break;
        m = p;
    }
}

void build_h()
{
    int i, j, hh = 0;
    For(i, n) rk[sa[i]] = i;
    For(i, n)
    {
        if (hh) hh--;
        int j = sa[rk[i] - 1];
        while (s[i + hh] == s[j + hh]) hh++;
        h[rk[i]] = hh;
    }
}

int lens;

///连接两字符串
inline void cat()
{
    lens = strlen(s);
    s[lens] = '$', s[lens + 1] = 0;
    strcat(s, s2);
    n = strlen(s);
}

int main()
{
    int ans, i;
    while (gets(s), gets(s2))
    {
        cat();
        build_sa(127), build_h();
        ans = 0;
        Forr(i, 1, n) if ((sa[i] < lens) != (sa[i - 1] < lens)) ans = max(ans, h[i]);
        PI(ans);
    }
    return 0;
}

相似题目:
POJ 2217 Secretary
POJ 2774 Long Long Message
URAL 1517 Freedom of Choice

Comments

comments powered by Disqus