absi2011's Blog & Daily Life.

其实我觉得代码是对的..

反正..

后缀数组写对了..

后面st表..

这一题是个后缀数组

立下flag:在最近的8天里,每日blog至少一更碎碎念

好久没AC题目了..

普通的题做不出来,只好回去做点模版题什么的

模版题还能WA一次自己还是太弱了..

求后缀数组代码是O(n log^2n)的..

void dfs(int t,int n)
{
    if (t>n) return;
    int i;
    for (i=0;i<n;i++)
    {
        if ((i==0)||(b[i-1]<b[i]))
        {
            c[b[i].id]=i;
        }
        else
        {
            c[b[i].id]=c[b[i-1].id];
        }
    }
    for (i=0;i<n;i++)
    {
        b[i].x=c[b[i].id];
    }
    for (i=0;i<n;i++)
    {
        if (b[i].id+t<n)
        {
            b[i].y=c[b[i].id+t];
        }
        else
        {
            b[i].y=-1;
        }
    }
    sort(b,b+n);
    dfs(t*2,n);
}

代码:

一道后缀数组的模版题