POJ2406 Power Strings 后缀数组(DC3算法)或KMP或暴搜(瞎写)

方法一：暴搜。。（188ms）

自己瞎写的。。竟然过了？？！！！

附上AC代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
typedef pair<int,int>pp;
#define mkp make_pair
#define pb push_back
const int INF=0x3f3f3f3f;
const ll MOD=1e9+(ll)7;

const int MAX=1e6+5;
char s[MAX];
int n;
int main()
{
    while(scanf("%s",s)==1)
    {
        if(strcmp(s,".")==0)
            break;
        n=strlen(s);
        int ans,l;
        for(l=1;l<n;l++)
        {
            if(n%l!=0)
                continue;
            int j=0,k=l;
            bool sign=true;
            while(k<n)
            {
                while(s[k]==s[j]&&j<l)
                    j++,k++;
                if(j<l)
                {
                    sign=false;
                    break;
                }
                j=0;
            }
            if(sign)
            {
                ans=n/l;
                break;
            }
        }
        if(l==n)
            ans=1;
        printf("%d\n",ans);
    }
	return 0;
}

方法二：后缀数组（2922ms）

果然我还是太菜了。。对各个数组的理解也不够。。

附上参考博客Orz：https://blog.****.net/superxtong/article/details/52082133

主要就是那几个判断条件，我还是把后缀树画出来了，写了一些理解，如下图： POJ2406 Power Strings 后缀数组(DC3算法)或KMP或暴搜(瞎写)

这道题用倍增会TLE，只好用DC3了（第一次用...），正好记录下来当模板了hiahiahia

附上AC代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
typedef pair<int,int>pp;
#define mkp make_pair
#define pb push_back
const int INF=0x3f3f3f3f;
const ll MOD=1e9+(ll)7;

const int MAX=1e6+5;
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[MAX*3],wb[MAX*3],wv[MAX*3],wss[MAX*3];
int c0(int *r,int a,int b)
{
    return (r[a]==r[b])&&(r[a+1]==r[b+1])&&(r[a+2]==r[b+2]);
}
int c12(int k,int *r,int a,int b)
{
    if(k==2)
        return (r[a]<r[b])||(r[a]==r[b]&&c12(1,r,a+1,b+1));
    else
        return (r[a]<r[b])||(r[a]==r[b]&&wv[a+1]<wv[b+1]);
}
void sor(int *r,int *a,int *b,int n,int m)
{
    int i;
    for(i=0;i<n;i++) wv[i]=r[a[i]];
    for(i=0;i<m;i++) wss[i]=0;
    for(i=0;i<n;i++) wss[wv[i]]++;
    for(i=1;i<m;i++) wss[i]+=wss[i-1];
    for(i=n-1;i>=0;i--) b[--wss[wv[i]]]=a[i];
}
void dc3(int *r,int *sa,int n,int m)
{
    int i,j,*rn=r+n;
    int *san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0;i<n;i++)
        if(i%3!=0)
            wa[tbc++]=i;
    sor(r+2,wa,wb,tbc,m);
    sor(r+1,wb,wa,tbc,m);
    sor(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc) dc3(rn,san,tbc,p);
    else for(i=0;i<tbc;i++) san[rn[i]]=i;
    for(i=0;i<tbc;i++)
        if(san[i]<tb)
            wb[ta++]=san[i]*3;
    if(n%3==1)
        wb[ta++]=n-1;
    sor(r,wb,wa,ta,m);
    for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
    for(i=0,j=0,p=0;i<ta&&j<tbc;p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(;i<ta;p++) sa[p]=wa[i++];
    for(;j<tbc;p++) sa[p]=wb[j++];
}
int sa[MAX*3];
int ran[MAX*3];
int height[MAX*3];
void da(int str[],int n,int m)
{
    for(int i=n;i<n*3;i++)
        str[i]=0;
    dc3(str,sa,n+1,m);
    int i,j,k=0;
    for(i=0;i<=n;i++)
        ran[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k) k--;
        j=sa[ran[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[ran[i]]=k;
    }
}

int r[MAX*3];//要*3
char s[MAX];
int main()
{
    int n,m;
    while(scanf("%s",s)==1)
    {
        if(strcmp(s,".")==0)
            break;
        n=strlen(s);
        m=-1;
        for(int i=0;i<n;i++)
        {
            r[i]=s[i];
            m=max(m,r[i]);
        }
        memset(sa,0,sizeof(sa));
        memset(ran,0,sizeof(ran));
        memset(height,0,sizeof(height));
        da(r,n,m+1);//注意m+1
        /*for(int i=1;i<=n;i++)
            cout<<"i="<<i<<" sa="<<sa[i]<<endl;
        for(int i=1;i<=n;i++)
            cout<<"i="<<i<<" rank="<<ran[i]<<" sa[i-1]="<<sa[i-1]<<" sa[i]="<<sa[i]<<" height="<<height[i]<<endl;*/

        int l,ans;
        for(l=1;l<n;l++)//从小到大枚举长度
        {
            if(n%l!=0)
                continue;
            if(height[ran[0]]!=n-l)//第一个和第二个的最长公共前缀不符合条件 //此判断省略也能过
                continue;
            int p=0,k=l;
            bool sign=true;
            while(k<n)
            {
                if(ran[p]-ran[k]!=1)//起始位置的rank要相邻
                {
                    sign=false;
                    break;
                }
                else
                    p=k,k+=l;
            }
            if(sign)
            {
                ans=n/l;
                break;
            }
        }
        if(l==n)
            ans=1;
        printf("%d\n",ans);
    }
	return 0;
}

方法二：KMP（157ms）

这道题说实话我真没想到用KMP。。先附上大佬博客Orz：

https://blog.****.net/wxw15617488718/article/details/77494159

其中这段总结的很好：KMP最小循环节、循环周期：

定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]（注意是len），子串为S[0…len-next[len]-1]。（next数组存的是最长相等的前缀和后缀字串长度）

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。

（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

附上AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=1e6+5;
char s[MAX];
int len;
int nex[MAX];
void get_nex()
{
    memset(nex,0,sizeof(nex));
    int j=0,k=-1;
    nex[0]=-1;
    while(j<len)
    {
        while(k!=-1&&s[j]!=s[k])
            k=nex[k];
        j++;k++;
        nex[j]=k;
    }
}
int main()
{
    while(scanf("%s",s)==1)
    {
        if(strcmp(s,".")==0)
            break;
        len=strlen(s);
        get_nex();
        int l=len-nex[len];
        //cout<<"nex[len]="<<nex[len]<<" l="<<l<<endl;
        if(len%l==0)
            printf("%d\n",len/l);
        else
            printf("1\n");
    }
	return 0;
}

POJ2406 Power Strings 后缀数组(DC3算法)或KMP或暴搜(瞎写)

相关推荐