-
Notifications
You must be signed in to change notification settings - Fork 5
/
gsais.h
122 lines (103 loc) · 3.19 KB
/
gsais.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// vim: noai:ts=2:sw=2
/*
* Authors: Felipe A. Louza, Simon Gog, Guilherme P. Telles
* contact: louza@ic.unicamp.br
* 03/04/2017
*/
/*
* This code is a modification of SA-IS algorithm by G. Nong et al., which can be
* retrieved at: http://code.google.com/p/ge-nong/
*
* Our version of SA-IS, called gSAIS, maintain the theoretical bounds of the
* original algorithm to construct the generalized suffix array.
*
* Our algorithm gSAIS can also computes the LCP-array and the Document-array
* with no additional costs.
*
* gsais(s, SA, NULL, NULL, n) //computes only SA
* gsais(s, SA, LCP, NULL, n) //computes SA and LCP
* gsais(s, SA, NULL, DA, n) //computes SA and DA
* gsais(s, SA, LCP, DA, n) //computes SA, LCP and DA
*
*/
/******************************************************************************/
#ifndef GSAIS_H
#define GSAIS_H
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <inttypes.h>
#include <string.h>
#include <time.h>
#define max(a,b) ((a) > (b) ? (a) : (b))
#ifndef DEBUG
#define DEBUG 0
#endif
#ifndef M64
#define M64 0
#endif
#if M64
typedef int64_t int_t;
typedef uint64_t uint_t;
#define PRIdN PRId64
#define U_MAX UINT64_MAX
#define I_MAX INT64_MAX
#define I_MIN INT64_MIN
#else
typedef int32_t int_t;
typedef uint32_t uint_t;
#define PRIdN PRId32
#define U_MAX UINT32_MAX
#define I_MAX INT32_MAX
#define I_MIN INT32_MIN
#endif
/*! @option type of s[0,n-1] for integer alphabets
*
* @constraint sizeof(int_t) >= sizeof(int_text)
*/
typedef uint32_t int_text; //4N bytes for s[0..n-1]
#define PRIdT PRIu32
/*! @option type for array DA
*/
typedef uint_t int_da;
/******************************************************************************/
/** @brief computes the suffix array of string s[0..n-1]
*
* @param s input string with s[n-1]=0
* @param SA suffix array
* @param n string length
* @return -1 if an error occured, otherwise the depth of the recursive calls.
*/
int sais(unsigned char *s, uint_t *SA, uint_t n);
/** @brief computes the suffix array of string s[0..n-1]
*
* @param k alphabet size+1 (0 is reserved)
*/
int sais_int(int_text *s, uint_t *SA, uint_t n, uint_t k);
/******************************************************************************/
/** @brief Computes the suffix array SA (LCP, DA) of T^cat in s[0..n-1]
*
* @param s input concatenated string, using separators s[i]=1 and with s[n-1]=0
* @param SA Suffix array
* @param LCP LCP array
* @param DA Document array
* @param n String length
* @param K alphabet size
*
* @return depth of the recursive calls.
*/
int gsais(unsigned char *s, uint_t *SA, int_t *LCP, int_da *DA, uint_t n);
/** @brief Computes the suffix array SA (LCP, DA) of T^cat in s[0..n-1]
*
* @param s input concatenated string, using separators s[i]=1 and with s[n-1]=0
* @param SA Suffix array
* @param LCP LCP array
* @param DA Document array
* @param n String length
* @param k alphabet size+2 (0 and 1 are reserved)
*
* @return depth of the recursive calls.
*/
int gsais_int(int_text *s, uint_t *SA, int_t *LCP, int_da *DA, uint_t n, uint_t k);
/******************************************************************************/
#endif