[后缀数组][模板] 求正好出现k次子串个数 HDU6194 string string string

Huh，比赛的时候花了三个小时把这个正解是用后缀自动机的题肝了出来，我也不知道我怎么做到的。

想了很多策略之后发现自己是错的就很难受，最后终于想到正确策略：在height数组上做一个长度为k的滑窗，每次检查滑窗两端点之外的height是否比这一整段内的最小值大，注意这里面的一整段最小值M就是这一整段的公共最长公共前缀的长度，这个东西和他的前缀是在这里出现了k次的，那么怎么知道他是不是在滑窗外面出现呢，和两端点的height比较一下就行了，取两端点中的最大值P，这个说明是之外的点与滑窗两个端点的最大公共前缀，而所有的在滑窗内的满足P<len<=M的前缀都是仅出现了一次的子串！！！

wa的话，需要特判k为1的情况，，因为height这个数组是个间隔定义的东西，所以这种只有一个的需要单独处理，这时候实际上区间内的最长公共前缀就是排名在此的后缀本身

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=2e6+100;
//const int MOD=1e9+7;
const int INF=0x4f4f4f4f;
const int maxnode=6e6+5;

void read(int &x)
{
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
}

//r从0到n-1存要处理的串变成正整数之后的样子，然后给r[n]=0，但是传进da的时候还是
//要n+1！！！！
//sa从1到n，取值为0到n-1，为排第几的是哪一个后缀
//rak，i从0到n-1，代表后缀i排第几！
//height从2到n代表sa[i-1] sa[i]的最长公共前缀
int wa[maxn],wb[maxn],wv[maxn],_ws[maxn];
int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)//用的时候n传进来要+1！！！！！！
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i=0; i--)
        sa[--_ws[x[i]]]=i;
    for(j=1,p=1; p=j)
                y[p++]=sa[i]-j;
        for(i=0; i=0; i--)
            sa[--_ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; ib)
    {
        t=a;
        a=b;
        b=t;
    }
    return(height[askRMQ(a+1,b)]);
}

char str[maxn];
int s[maxn];
int sa[maxn];
int cnt[maxn];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T,k,n,m=30;
    LL ans;
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        //memset(cnt,0,sizeof(cnt));
        //memset(RMQ,0,sizeof(RMQ));
        scanf("%d",&k);
        getchar();
        gets(str);
        n=strlen(str);
        if(k>n)
        {
            printf("0\n");
            continue;
        }
        for (int i=0; imxt)
                {
                    ans++;
                    tm--;
                }

            }
        }
        else//k==1特判
        {
            for (int i=1; i<=n; i++)
            {
                int a=sa[i];
                int tm=n-a;//这时候就是他本身了
                int mxt=max(height[i],height[i+1]);
                while(tm>mxt)
                {
                    tm--;
                    ans++;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

发表回复 取消回复

发表回复取消回复