前言：雖然這題前面加了個括號是“省選模擬30”，但是在accoders上是比賽“省選模擬31”里面的，
題目描述
題解
先貼出官方正解，是用的和后綴陣列：
根據“萬串皆可后綴機”的套路，這題我還是選擇用后綴自動機(SAM)做，容易發現一個串的最小表示包含的資訊等價于每個位置記錄它前面第一個與它相同的字符出現位置的距離，比如“reverse”和“abcbadb”都可以表示為“0,0,0,2,4,0,3”（為了方便，直接記這種表示為“最小表示”），所以可以得到一個做法，把所有子串插入廣義SAM里面（自動去重），然后遍歷一遍統計答案，
接下來，問題變為怎么盡可能少地插入子串，也就是讓插入的串盡可能多地包含其它子串，因為一個子串相當于原串掐頭去尾，而前面去掉的部分會影響后面的“最小表示”，所以我們考慮從后往前維護每一個后綴的最小表示，具體就是記錄每一種字符在后面出現的第一個位置，與當前字符比較，然后更新后面的“最小表示”，
假設當前維護到第 i 個字符為 c，分兩種情況：
- i 后面沒有出現 c，那么除了 i 處的最小表示為 0 之外，其它位置不變，不會影響 i+1~n 的最小表示；
- i 后面出現的第一個 c 位置為 j ，那么除了 i 處最小表示為 0 、j 處最小表示為 j-i 之外，其它位置不變，不會影響 i+1~j-1 和 j+1~n 的最小表示，
由于子串倒轉后統計結果不變，我們可以把最小表示倒著插入，記錄每個后綴在SAM上的對應節點為，
- 那么對于第一種情況，從
處再插入一個 0 即可；
- 對于第二種情況，從
處倒著插入一遍 i~j 的最小表示即可，
演算法可行的關鍵在于第二種情況的插入次數，因為對于每一種字符，最多使其插入 n 次，所以總共插入不超過 nm 次，
但是做到這里還沒完，當我們在第二種情況進行插入時，更改后的 i+1~j 的子串是不存在的，因為當且僅當子串中包含 i 時 j 的最小表示為 j-i ，怎么在統計時去掉這些子串呢？
由于上每個節點的子樹存了該節點代表的子串的所有右端點位置，換過來就是插入時我們希望算入的子串的左端點位置，這時我們可以在插入時記錄每個端點是否合法（比如在第二種情況中，只有 i 作為左端點時合法），統計時只統計子樹中包含合法右端點的節點即可，
由于插入的是數字，故用map儲存SAM上的邊，總時間復雜度為，
代碼
評測要帶freopen
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#define ll long long
#define uns unsigned
#define MAXN 50005
#define INF 0x3f3f3f3f
using namespace std;
inline ll read(){
ll x=0;bool f=1;char s=getchar();
while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
return f?x:-x;
}//SAM
struct SAM{
map<int,int>ch;int len,fa;
SAM(){len=fa=0,ch.clear();}
}sam[MAXN<<5];
int tot=1,la[MAXN],num[MAXN<<5];
inline bool fd(int id,int c,int x){
return sam[id].ch.find(c)!=sam[id].ch.end()&&sam[id].ch[c]==x;
}
inline int samadd(int c,int las,int ad){
int p=las,np=las=++tot;sam[np].len=sam[p].len+1;
for(;p&&sam[p].ch[c]==0;p=sam[p].fa)sam[p].ch[c]=np;
if(!p)sam[np].fa=1;
else{int q=sam[p].ch[c];
if(sam[q].len==sam[p].len+1)sam[np].fa=q;
else{
int nq=++tot;sam[nq]=sam[q],sam[nq].len=sam[p].len+1,sam[q].fa=sam[np].fa=nq;
for(;p&&fd(p,c,q);p=sam[p].fa)sam[p].ch[c]=nq;
}
}num[np]+=ad;
return np;
}//main
int n,m,si[15],id[MAXN];
ll ans;
char s[MAXN];
vector<int>G[MAXN<<5];
inline int dfs(int x){
int nu=num[x];
for(uns i=0;i<G[x].size();i++)nu+=dfs(G[x][i]);
if(x>1&&nu>0)ans+=sam[x].len-sam[sam[x].fa].len;
return nu;
}
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
n=read(),m=read();
scanf("%s",s+1),la[n+1]=1;
for(int i=n;i>0;i--){
if(si[s[i]-'a']){
int k=si[s[i]-'a'];id[k]=k-i;
for(int j=k;j>=i;j--)la[j]=samadd(id[j],la[j+1],j==i);
}
else la[i]=samadd(id[i],la[i+1],1);
si[s[i]-'a']=i;
}
for(int i=2;i<=tot;i++)G[sam[i].fa].push_back(i);
dfs(1);
printf("%lld\n",ans);
return 0;
}由于多數人用的是沒被卡掉的空間小的，我的空間顯得格外突兀：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272780.html
標籤：其他