poj 2406 Power Strings (后缀数组||kmp)

Posted by 111qqz on Tuesday, August 2, 2016

TOC

poj 2406

题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的,
求 R 的最大值

思路:论文题.

转载论文中的题解:

最关键的在加黑的那句话:看 suffix(1)和 suffix(k+1)的最长公共
前缀是否等于 n-k

why???

转载一段证明:

虽然这道题不适合用后缀数组做,倍增会tle,dc3也是卡时间才能过,但是接触到了一个想法.

要看一个字符串s能否由一个较小的长度为k的字符串t重复若干次得到,除了要整除以外,

gengxin判断suffix(1)和 suffix(k+1)的最长公共****前缀是否等于 n-k即可.

下面是用倍增写的tle了的代码,价值在于那段没有用rmq,而是o(n)更新height数组到height[rk[0]]之间的最小值要怎么写.

/* ***********************************************
Author :111qqz
Created Time :2016年08月02日 星期二 19时41分08秒
File Name :code/poj/2406.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E6+7;
int n,sa[N],rk[N],t[N],t2[N],cnt[N];
int height[N];
char s[N];
int cmp( int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getSa( int n,int m)
{
    int *x=t;
    int *y=t2;
    ms(cnt,0);
    for ( int i = 0 ; i < n;  i++) cnt[x[i]=s[i]]++;
    for ( int i = 1;  i < m ; i++) cnt[i]+=cnt[i-1];
    for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i ;
    for ( int k = 1 ; k <= n ; k<<=1)
    {
    int p = 0;
    for ( int i = n- k; i < n ; i++) y[p++] =i;
    for ( int i = 0 ; i < n;  i++) if (sa[i]>=k) y[p++] = sa[i]-k;
    ms(cnt,0);
    for ( int i = 0 ; i < n ; i++) cnt[x[y[i]]]++;
    for ( int i = 0 ; i <m ; i ++) cnt[i]+=cnt[i-1];
    for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
    swap(x,y);
    p = 1;
    x[sa[0]] = 0 ;
    for ( int i = 1; i  <n ; i++)
        x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
    if (p>=n) break;
    m = p;
    }
}
void getHeight( int n)
{
    int k = 0 ;
    for ( int i = 0 ;i <n ; i++) rk[sa[i]] = i ;
    height[0] = 0 ;
    for ( int i = 0 ; i < n;  i++)
    {
    if (rk[i]==0) continue;
    if (k)  k--;
    int j = sa[rk[i]-1];
    while (s[i+k]==s[j+k]) k++;
    height[rk[i]] = k ;
    }
}
int getSuffix( char s[])
{
    int up = 0 ;
    int len = strlen(s);
    for ( int i = 0 ; i < len; i++)
    {
    int val = s[i];
    up = max(up,val);
    }
    s[len++] = '$' ;
    getSa(len,up+1);
    getHeight(len);
    return len;
}

int lcp[N];
int solve( int n)
{
    int st = rk[0];
    lcp[st] = inf;
    for ( int i = st-1 ; i ; i--)
    lcp[i] = min(lcp[i+1],height[i+1]);
    for ( int i = st+1 ; i <= n ; i++)
    lcp[i] = min(lcp[i-1],height[i]);

    for ( int k = 1 ; k <= n ; k++)
    if (n%k==0)
        if (lcp[rk[k]]==n-k)
        return n/k;

    return 1;

}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    while (~scanf("%s",s))
    {
        if (s[0]=='.') break;
        int len = getSuffix(s);
        cout<<endl;
        int ans = solve(len-1);

//	    for ( int i = 0 ; i < len; i++) cout<<"i:"<<i<<" height[i]:"<<height[i]<<" rk[i]:"<<rk[i]<<" lcp[i]"<<lcp[i]<<endl;
        printf("%d\n",ans);
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

kmp的思路:

这道题用kmp非常块…

但是其实…………

其实………..

其实我不会kmp………………….

搞完后缀数组去学下.

/* ***********************************************
Author :111qqz
Created Time :2016年08月02日 星期二 21时27分44秒
File Name :code/hdu/r2406.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E6+7;
int nxt[N];
char s[N];
void kmp(int n)
{
    int i = 0,j=-1;
    nxt[0] = -1;
    while (i<n)
    if (j==-1||s[i]==s[j]) nxt[++i] = ++j;
    else j = nxt[j];
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    while (~scanf("%s",s))
    {
        if (s[0]=='.') break;
        int len = strlen(s);
        kmp(len);
        int k = len-nxt[len];
        printf("%d\n",len%k?1:len/k);

    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付