主函數(shù)
int main()
{
scanf("%s",st);
int len = strlen(st);
for(int i = 0; i < len; i++) r[i] = st[i];
r[len] = 1;
for(int i = 0; i < len; i++) r[i+len+1] = st[len-1-i];
int n = 2*len+1;
r[n] = 0;
da(r, sa, n+1, 128);
Get_Height(r, sa, n);
for(int i = 1; i <= n; i++) RMQ[i] = height[i];
initRMQ(n);
/**此處添加功能函數(shù)**/
}
1纹腌、最長(zhǎng)公共前綴
height 數(shù)組：定義 height[i] = (suffix(sa[i-1]), suffix(sa[i]))最長(zhǎng)公共前綴工坊，也就是排名相鄰的兩個(gè)后綴的最長(zhǎng)公共前綴妓布。
int rank[M], height[M];
void calheight(int *r, int *sa, int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
寫(xiě)法二
void Get_Height(int str[], int sa[], int Rank[], int Height[], int n)//計(jì)算Height值
{
int k = 0;
for(i = 0; i <= n; i++) Rank[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[Rank[i]-1];
while(str[i+k] == str[j+k]) k++;
height[Rank[i]] = k;
}
}
2、單個(gè)字符串的相關(guān)問(wèn)題
常用做法是先求后綴數(shù)組和 height 數(shù)組，然后利用 height數(shù)組進(jìn)行求解奴璃。
-
重復(fù)子串(串 R 在串 L 中至少出現(xiàn)兩次推励，稱 R 是 L 的重復(fù)子串鹤耍。)
//可重疊
int height[M];
void CHONG(int *H, int n)
{
int maxx = 0;
for (int i = 1; i <= n; i++)
maxx = max(maxx, H[i]);
}
//不可重疊(二分答案，判斷是否存在長(zhǎng)度相同的兩個(gè)子串验辞，且不重疊)
bool check(int *sa,int n,int k)
{
int maxx=sa[1], minn=sa[1];
for(int i = 2; i <= n; i++)
{
if(height[i] < k) maxx = minn = sa[i];
else
{
minn = min(minn, sa[i]);
maxx = max(maxx, sa[i]);
if(maxx-minn > k) return true;
}
}
return false;
}
void solve(int *sa, int n)
{
L = 1;
R = n/2;
while(L <= R)
{
mid = (L + R)/2;
if(check(sa, n, mid)) L = mid+1;
else R = mid-1;
}
if(R >= 4) printf("%d\n", R+1);
else printf("0\n");
}
/*可重復(fù)K次（判斷是否存在一個(gè)組的后綴個(gè)數(shù)不小于 k稿黄。如果有，便存在k 個(gè)相同的子串滿足條件跌造，否則不存在杆怕。）*/
bool check(int n, int k, int mid)
{
int s = 1;
for(int i = 1; i <= n; i++)
{
if(height[i] >= mid)
{
s++;
if(s >= k) return true;
}
else s = 1;
}
return false;
}
void solve(int *sa, int n)
{
int L = 1;
int R = n/2;
while(L <= R)
{
int mid = (L + R)/2;
if(check(sa, n, mid)) L = mid+1;
else R = mid-1;
}
printf("%d\n", R);
}
-
子串的個(gè)數(shù)
給定一個(gè)字符串，判斷其中存在多少子串（可以用字典樹(shù)）
/*對(duì)于每一次新加進(jìn)來(lái)的后綴 suffix(sa[k]), 將產(chǎn)生 n-sa[k]+1 個(gè)新的前綴壳贪。
但是其中有height[k]個(gè)是和前面的字符串的前綴是相同的陵珍。
所以 suffix(sa[k])將“貢獻(xiàn)”出 n-sa[k]+1- height[k]個(gè)不同的子串。*/
LL Get_Kind(int *height, int n)
{
ans =(LL)n * (n+1) / 2;
for(int i = 1; i <= n; i++)
ans -= height[i];
return ans;
}
-
回文子串（也可用回文樹(shù)）
//求所有后綴之間的不相同的前綴的個(gè)數(shù)
//最長(zhǎng)回文字串
/*求一個(gè)后綴 和 一個(gè)反過(guò)來(lái)寫(xiě)的后綴 的最長(zhǎng)公共前綴
將整個(gè)字符串反過(guò)來(lái)寫(xiě)在原字符串后面违施，中間用一個(gè)特殊的字符隔開(kāi)
問(wèn)題變?yōu)榍筮@個(gè)新的字符串的某兩個(gè)后綴的最長(zhǎng)公共前綴
栗子：
字符串banana
新串 banana#ananab
后綴 na#ananab與na#ananab的公共前綴na
后綴 ana#ananab與anab的公共前綴ana
...
*/
void solve()
{
int k, w, ans;
for(int i = 0; i < len; i++)//窮舉每一位互纯，計(jì)算以這個(gè)字符為中心的最長(zhǎng)回文子串
{
k = LCP(i, n-i);
if(k*2 > ans) //偶對(duì)稱
{
ans = k*2;
w = i-k;
}
k = LCP(i, n-i-1);
if(k*2-1 > ans) //奇對(duì)稱
{
ans = k*2-1;
w = i-k+1;
}
}
st[w+ans] = 0;
printf("%s\n",st+w);
}
-
連續(xù)重復(fù)子串
定義：：如果一個(gè)字符串 L 是由某個(gè)字符串 S 重復(fù) R 次而得到的，則稱L 是一個(gè)連續(xù)重復(fù)串磕蒲。R 是這個(gè)字符串的重復(fù)次數(shù)伟姐。
步驟：
1收苏、窮舉字符串 S 的長(zhǎng)度 k，判斷其是否滿足愤兵。
判斷過(guò)程：
字符串 L 的長(zhǎng)度能否被 k 整除鹿霸，
suffix(1)和 suffix(k+1)的最長(zhǎng)公共前綴是否等于 n-k
2、因?yàn)閟uffix(1)是固定的秆乳，預(yù)處理RMQ問(wèn)題懦鼠，求出height 數(shù)組中的每一個(gè)數(shù)到
height[rank[1]]之間的最小值即為最長(zhǎng)公共前綴
int RE(int n)
{//窮舉長(zhǎng)度L，看字符 r[L*i]和 r[L*(i+1)]往前和往后各能匹配到多遠(yuǎn)
int ans = 0;
int k, now, step;
for(int i = 1; i < n; i++)
{
for(int j = 0; j+i < n; j += i)
{
k = LCP(j, j+i);
now = k / i;
step = j - (i-k%i);
if(step>=0 && LCP(step, step+i)>=(i-k%i)) now++;
if(now > ans) ans = now;
}
}
return ans+1;
}
3屹堰、兩個(gè)字符串的相關(guān)問(wèn)題
先連接這兩個(gè)字符串肛冶，然后求后綴數(shù)組和height 數(shù)組，再利用 height 數(shù)組進(jìn)行求解
A：aabba
B：aab
新串： aabba#aab
對(duì)新串進(jìn)行SA處理
-
公共字串（同時(shí)出現(xiàn)在字符串 A 和字符串 B 中的字符串L）
給定兩個(gè)字符串 A 和 B扯键，求最長(zhǎng)公共子串睦袖，等于求‘A的后綴’和‘B的后綴’的最長(zhǎng)公共前綴 的最大值。
將第二個(gè)字符串寫(xiě)在第一個(gè)字符串后面荣刑，中間用一個(gè)未出現(xiàn)過(guò)的字符隔開(kāi)馅笙，再求這個(gè)新的字符串的后綴數(shù)組。
求height[i]的最大值厉亏，但是要注意董习，只有suffix(sa[i-1])和suffix(sa[i])不是同一個(gè)字符串中的兩個(gè)后綴時(shí)，height[i]才是滿足條件的爱只。
void solve(int *sa, int *height, int n)
{
for(int i = 2; i <= n; i++)
if(height[i] > ans)
if((j<sa[i-1]&&j>sa[i]) || (j>sa[i-1]&&j<sa[i]))
ans = height[i];
printf("%d\n",ans);
}
-
子串的個(gè)數(shù)(不懂QAQ)
計(jì)算 A 的所有后綴和 B 的所有后綴之間的最長(zhǎng)公共前綴的長(zhǎng)度皿淋，把最長(zhǎng)公共前綴長(zhǎng)度不小于 k 的部分全部加起來(lái)。
步驟：
按 height 值分組恬试，求每組中后綴之間的最長(zhǎng)公共前綴之和
掃描一遍窝趣，每遇到一個(gè) B 的后綴就統(tǒng)計(jì)與前面的 A 的后綴能產(chǎn)生多少個(gè)長(zhǎng)度不小于 k 的公共子串，這里 A 的后綴需要用一個(gè)單調(diào)的棧來(lái)高效的維護(hù)训柴。然后對(duì) A 也這樣做一次哑舒。
//長(zhǎng)度不小于 k 的公共子串的個(gè)數(shù)
int f[M], a[M], b[M],;
void solve(int *height, int *sa)
{
for(int i = 2; i <= n; i++)
{
f[i] = sa[i] < l;
height[i] -= k-1;
if(height[i] < 0) height[i] = 0;
}
height[n+1] = 0;
a[0] = -1;
LL ans = 0;
for(int t = 0; t <= 1; t++)
{
int c = 0;
LL ss = 0;
for(int i = 2; i <= n; i++)
{
if(f[i]!=t) ans += ss;
c++;
a[c] = height[i+1];
b[c] = f[i]==t;
ss += (LL)a[c] * b[c];
while(a[c-1] >= a[c])
{
ss -= (LL)(a[c-1]-a[c]) * b[c-1];
a[c-1] = a[c];
b[c-1] += b[c];
c--;
}
}
}
printf("%I64d\n",ans);
}
4、多個(gè)字符串的相關(guān)問(wèn)題 多個(gè)字符串的相關(guān)問(wèn)題 多個(gè)字符串的相關(guān)問(wèn)題
先將所有的字符串連接起來(lái)畦粮，，中間用不相同的且沒(méi)有出現(xiàn)在字符串中的字符隔開(kāi)乖阵，然后求后綴數(shù)組和 height 數(shù)組宣赔，再利用 height 數(shù)組進(jìn)行求解。這中間可能需要二分答案瞪浸。
//主函數(shù)
int main()
{
int T_T;
scanf("%d", &T_T);
while(T_T--)
{
int n_n;
scanf("%d", &n_n);
int len = 0;
for(int i = 1; i <= n_n; i++)
{
scanf("%s", str);
int k = strlen(str);
for(int j = 0; j < k; j++)
{
r[j+len] = str[j] +10;
who[j+len] = i;
}
r[len+k] = i;
who[len+k] = 0;
len += k+1;
}
len--;
r[len] = 0;
da(r, sa, len+1, 138);
Cal_Height(r, sa, len);
height[len+1] = -1;
solve();
}
}
不小于 k 個(gè)字符串中的最長(zhǎng)子串
通過(guò)height數(shù)組進(jìn)行分組儒将，判斷每組的后綴是否出現(xiàn)在不小于 k 個(gè)的原串中。
int who[maxn],yes[101]= {0},ii=0;
int n, nn, ss, ii;
int ans[maxn];
bool check(int mid, int len)
{
bool flag = false;
int j;
for (int i = 2; i <= len; i=j+1)
{
while(height[i]<mid && i<=len) i++;
j = i;
while (height[j] >= mid) j++;
ii++;
int s = 0;
for (int k = i-1; k < j; k++)
if ((t=who[sa[k]]) != 0)
if (yes[t] != ii) yes[t]=ii,s++;
if (s >= nn)
{
if(flag) ans[++ss] = sa[i-1];
else
{
ans[ss=1] = sa[i*1];
flag = true;
}
}
}
return flag;
}
void solve(int flag, int len)
{
int nn = n/2+1;
int L = 1;
int R = 1000;
while (L <= R)
{
int mid = (L + R) >> 1;
if (check(mid, len)) L = mid + 1;
else R = mid -1;
}
if(flag) printf("\n");
else flag = 1;
if (L == 0) printf("?\n");
else
{
for (int i = 0; i <= ss; i++)
{
int tmp = ans[i];
for (int j = 0; j < R; j++)
printf("%c", r[tmp+k]-100);
printf("\n");
}
}
}
每個(gè)字符串至少出現(xiàn)兩次且不重疊的最長(zhǎng)子串
int who[maxn],min[11],max[11];
int len,n;
int check(int mid)
{
int i,j,k;
for(i=2; i<=len; i=j+1)
{
for(; height[i]<mid && i<=len; i++);
for(j=i; height[j]>=mid; j++);
if(j-i+1<n) continue;
for(k=1; k<=n; k++)
{
min[k]=1000000;
max[k]=-1;
}
for(k=i-1; k<j; k++)
{
if(sa[k]<min[who[sa[k]]]) min[who[sa[k]]]=sa[k];
if(sa[k]>max[who[sa[k]]]) max[who[sa[k]]]=sa[k];
}
for(k=1; k<=n; k++) if(max[k]-min[k]<mid) break;
if(k>n) return 1;
}
return 0;
}
char st[110];
void solve()
{
int L = 1;
int R = 5000;
while (L <= R)
{
int mid = (L + R) >> 1;
if (check(mid)) L = mid + 1;
else R = mid - 1;
}
printf("%d\n", R);
}
出現(xiàn)或反轉(zhuǎn)后出現(xiàn)在每個(gè)字符串中的最長(zhǎng)子串
//出現(xiàn)或反轉(zhuǎn)后出現(xiàn)在每個(gè)字符串中的最長(zhǎng)子串
