poj 2774 접미사 배열 템 플 릿

1536 단어 데이터 구조문자열
두 문자열 의 가장 긴 공통 문자열 을 구 합 니 다.
두 문자열 을 새 문자열 로 연결 하고 접미사 배열 과 높이 배열 lcp 를 계산 합 니 다.
그리고 접미사 배열 의 모든 인접 접 두 사 를 검사 합 니 다. 그 중에서 접 두 사 는 각각 첫 번 째 와 두 번 째 문자열 에 속 하 는 lcp 의 최대 값 이 답 입 니 다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxn 200005


int r[maxn];
int rank[maxn],height[maxn],sa[maxn]; 
//sa[1~n]    ,sa[0]   n
//height[2~n]    ，height[i]   S[sa[i-1]...] S[sa[i]...]       lcp
int t1[maxn],t2[maxn],c[maxn];//    
bool cmp(int *r, int a, int b, int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
//logn     ，O(nlogn)
void da(int *str,int n,int m) //n      ，m      
{
    n++;
    int i,j,p,*x=t1, *y=t2;
    for(i=0; i=0; i--) sa[--c[x[i]]]=i;
    for(j=1; j<=n; j<<=1){
        p=0;
        for(i=n-j; i=j) y[p++]=sa[i]-j;

        for(i=0; i=0; i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        for(i=1; i=n) break;
        m=p;
    }
    n--;
    int k=0;
    for(i=0; i<=n; i++) rank[sa[i]]=i;
    for(i=0; i
서버리스 Lambda에 My Probot 앱 배포
poj 1195

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage