后缀数组

POJ 3415 Common Substrings

Posted on

后缀数组 + 单调栈好题
网络赛时的后缀数组可以用这个思路解,但是我并不是很会,今天补上。

题意:
给你两个串,问你长度不小于 k 的重复子串的数量。

思路:
若只是对于一个字符串,问它长度不小于 k 的重复子串数量,那么考虑对height根据 k 分组,然后记录一下就可以了,将 height 去重后,每个 height 的贡献为 \( max ( 0, height - k +1 ) \) 个人猜测,后果不计

但这题是两个字符串,我们可以将两个字符串用一个特殊字符连接,并将后缀通过第一个字符串长度区分开来,对于同一个 height 组中,当前的 height 只能跟另一个 height 组相比求 lcp 。
一个可行的方法是,将组内不同的height都记录下来,再对于每一个当前height,我把它跟另一个height组一一求贡献。但是这个复杂度为 \( O ( n^2 ) \),显然是不行的。

最后学到的优化就是单调栈优化了,用 st[i][0]表示栈中第 i 号元素记录时候的height值,st[i][1]表示在这个height值上覆盖了st[i][1]个子串,在栈内维护height递增,实现\( O( 1 ) \) 求贡献。

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 5;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) 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 getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        DA(len + 1, 130);
        getHeight(len);
    }

    int st[maxn][2];
    void solve(int key, int limit)
    {
        ll tot = 0, top = 0, sum = 0;
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] < key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] > key)
                sum += tot;
        }
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] > key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] < key)
                sum += tot;
        }
        printf("%lld\n", sum);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int k;
    while (scanf("%d", &k) != EOF && k > 0) {
        scanf("%s", buf);
        int len = strlen(buf);
        buf[len] = '$';
        scanf("%s", buf + len + 1);
        suffix_array.input(buf);
        suffix_array.solve(len, k);
    }
    return 0;
}
单调栈

POJ 3494 Largest Submatrix of All 1’s

Posted on

题意:
给你一个矩阵 全由0,1组成 让你找出其中由1组成的面积最大的矩形
题意非常简单 但让人无从下手
其实如果我们一行一行处理 将矩阵转换到 柱状图 就有想法了
eg

1 0 1 00 0 1 0
0 1 1 1-->0 1 2 1
1 1 0 1-->1 2 0 2
1 0 1 12 0 1 3

再对每一行进行计算连续的最大矩形面积即可

我的方法是直接把 terrible set 的方法拉过来用的 事实证明 效率还好

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int row,col,ans,tw,temp,top;
int mat[2010][2010];

struct grid
{
    int wid,high;
    grid(int a=0,int b=1):high(a),wid(b){}
}st[2010];

void push(int h)
{
    tw=temp=0;
    while(top>0)
    {
        if(st[top].high>h)
        {
            tw+=st[top].wid;
            if((temp=tw*st[top].high)>ans)
                ans=temp;
            top--;
        }
        else break;
    }
    tw++;
    if((temp=tw*h)>ans) ans=temp;
    if(h)  st[++top]=grid(h,tw);
}

int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                scanf("%d",&mat[i][j]);
        for(int i=1; i<=col; i++)
            mat[0][i]=0;
        ans=0;
        for(int i=1; i<=row; i++)
        {
            top=0;
            for(int j=1; j<=col; j++)
                if(mat[i][j]) mat[i][j]+=mat[i-1][j];
            for(int j=1; j<=col; j++)
                push(mat[i][j]);
            tw=temp=0;
            while(top>0)
            {
                tw+=st[top].wid;
                if((temp=tw*st[top].high)>ans)
                    ans=temp;
                top--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}