程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3729 Facer’s string (後綴數組)

POJ 3729 Facer’s string (後綴數組)

編輯:C++入門知識

題目大意:

串1中有多少個後綴和 串2中的某個後綴 的lcp 為 k


思路分析:

先找出 長度至少為k的對數有多少。

再找出 至少為k+1的有多少

然後相減。


#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 110005
using namespace std;

int str[maxn];
int sa[maxn],t1[maxn],t2[maxn],c[maxn],n;
void suffix(int m)
{
    int *x=t1,*y=t2;
    for(int i=0; i=0; i--)sa[--c[x[i]]]=i;
    for(int k=1; k<=n; k<<=1)
    {
        int p=0;
        for(int i=n-k; i=k)y[p++]=sa[i]-k;
        for(int i=0; i=0; i--)sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;
        x[sa[0]]=0;
        for(int i=1; i=n)break;
        m=p;
    }
}
int rank[maxn],height[maxn];
void getheight()
{
    int k=0;
    for(int i=0; i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved