http://poj.org/problem?id=1509
http://www.spoj.com/problems/BEADS/

两种解法:

第一种方法,串的最小表示。核心思想是——双指针法——比较两个滑动的字符串,复杂度,实现见下。具体见周源论文《浅析“最小表示法”思想在字符串循环同构问题中的应用》。

第二种方法,LCP:

  1. 倍增字符串;
  2. 找第一个sa[i]在前半部分(sa[i] < lens)的i;
  3. while (height[i + 1] >= lens) ++i;
  4. printf(sa[i] + 1)。

串的最小表示:

/*0ms,216KB*/

char s[20005], s2[10005];

int smallestRepresationPos(char *s2)
{
    int i = 0, j = 1, k = 0, n = strlen(s2);
    strcpy(s, s2);
    strcat(s, s2);
    while (i < n && j < n && k < n)
    {
        if (i == j) j++;
        if (s[i + k] == s[j + k]) ++k;
        else s[i + k] > s[j + k] ? i += k + 1 : j += k + 1, k = 0;
    }
    return i;
}

int main()
{
    int t;
    SI(t), getchar();
    while (t--)
    {
        gets(s2);
        PI(smallestRepresationPos(s2) + 1);
    }
    return 0;
}

LCP:

/*32ms,624KB*/

const int mx = 20005;

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

/// m为最大字符值+1,一般为127,仅小写时123('z'+1),仅大写时91('Z'+1)
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;
    }
}

int rk[mx], h[mx];

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 main()
{
    int t, i, l, r, m;
    SI(t), getchar();
    while (t--)
    {
        gets(s2);
        m = strlen(s2), n = m << 1;
        strcpy(s, s2);
        strcat(s, s2);
        build_sa(123), build_h();
        Forr(i, 1, n + 1) if (sa[i] < m) break;
        while (h[i + 1] >= m) ++i;
        PI(sa[i] + 1);
    }
    return 0;
}

Comments

comments powered by Disqus