poj 2406連続サブストリング

2974 ワード

データ構造

パワースターリング
Time Limit: 3000 MS

メモリLimit: 65536 K
Total Submissions: 41110

Acceepted: 17099
Description
Given two stinings a and b we define a*b to be their concateation.For example、if="abc"andb="def"the n a*b="abcdef".If wethininininininininininininininininamltipcation、exponentiation=="aaaaatttttttttinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininin)
Input
Each test case is a line of input representing s,a string of printable characters.The length of s will be at least 1 and will not exceed 1 milion characters.A line containing a period follows the last test case.
Output
For each s you shoul d print the larget n such that=a^n for some string a.

/*
poj2406       

       ，                  

      DA  
                 ,     Rank[0] Rank[k]   n-k
(      ，0~k = k+1~2*k+1 ....          0~k     
     )
  MLE.     RMQ    ,                   。
           Rank[0],     rank[0]            
  DA  nlog(n)   TLE- -
        DC3   ，    2600ms

    kmp     (          )

hhh-2016-03-13 18:11:02
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef long double ld;
#define lson (i<<1)
#define rson ((i<<1)|1)
const int maxn = 2000001;

#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)=0; i--) b[--wsf[wv[i]]]=a[i];
    return;
}
void dc3(int *r,int *sa,int n,int m)
{
    int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0; i= 0;i--)
    {
        if(height[i+1] < rm[i+1]) rm[i] = height[i+1];
        else rm[i] = rm[i+1];
    }

    for(int i = to+1;i <= len;i++)
    {
        if(height[i] < rm[i-1]) rm[i] = height[i];
        else rm[i] = rm[i-1];
    }
}

int solve(int len)
{
    for(int i = 1;i <= len/2;i++)
    {
        if(len % i) continue;
        if(rm[Rank[i]] == len-i) return len/i;
    }
    return 1;
}

int main()
{
    while(scanf("%s",ts) != EOF)
    {
        if(ts[0] == '.')
            break;
        int len = strlen(ts);
        for(int i = 0; i < len; i++)
            str[i] = ts[i];
        str[len] = 0;

        dc3(str,sa,len+1,300);
        getheight(str,len);
        iniRMQ(len);
        printf("%d
",solve(len));
    }
    return 0;
}

328.Odd Even Linked List