P9089 「SvR-2」Work 题解

P9089 「SvR-2」Work

可以找到一些性质：

1. 如果串 \(c(字符)+A\) 合法则串 \(A\) 合法，反之如果串 \(A\) 不合法则串 \(c(字符)+A\) 不合法
2. 如果串 \(A,B\) 合法（\(len(A)<len(B)\)）且 \(c+A\) 合法，则 \(c+B\) 合法，而长度最小的合法串一定是一个后缀组成的

那么可以得到以下算法
用一个栈维护合法区间的右端点（实际记录的是后缀的哈希值）
从后往前遍历，对于点 &i&，将其视为左端点，如果以栈顶为右端点的串不能被一个后缀表示则退栈（直到栈为空）
此时以 \(i\) 为左端点的合法串的数量即为栈中元素的数量
最后将该点作为右端点加入栈中即可

用 \(set[i]\) 储存长度为 \(i\) 的后缀，即可判断是否能被一个后缀表示
时间复杂度\(O(nlogn)\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=2000006,M1=1e9+7,M2=1e9+1,D=2011111;

int n,cm1[N+10],cm2[N+10];
string s[N];
char cps[N];

//双哈希 
struct HAS{ int l,x,y; };
//bool operator<(const HAS& a,const HAS& b){ if(a.x^b.x) return a.x<b.x; else return a.y<b.y; }//set用 
HAS operator+(const HAS& a,const char& b){ return (HAS){a.l+1,(a.x*D%M1+b-'a')%M1,(a.y*D%M2+b-'a')%M2}; }//加入一个字符 
HAS operator-(const HAS& a,const HAS& b){ return (HAS){a.l-b.l,(a.x-b.x*cm1[a.l-b.l]%M1+M1)%M1,(a.y-b.y*cm2[a.l-b.l]%M2+M2)%M2}; }//a段减去 后面的 b段 
set<HAS>st[N];
HAS sta[N];
int top=0;

void init(){ cm1[0]=cm2[0]=1; for(int i=1;i<=1e6+10;i++) cm1[i]=cm1[i-1]*D%M1, cm2[i]=cm2[i-1]*D%M2; }
signed main(){
	
	init();
	
	scanf("%lld", &n);
	for(int i=1;i<=n;i++){ scanf("%s", cps); s[i]=cps; }
	
	//倒着插入每个后缀
	for(int i=1;i<=n;i++){
		int len=s[i].length();
		HAS cur=(HAS){0,0,0};
		for(int j=len-1;j>=0;j--){
			cur=cur+s[i][j];
			st[cur.l].insert(cur);
		}
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		HAS cur=(HAS){0,0,0};
		sta[top=1]=cur;
		int len=s[i].length();
		for(int j=len-1;j>=0;j--){
			cur=cur+s[i][j];
			while(top&&!st[cur.l-sta[top].l].count(cur-sta[top])) top--;//不满足则退栈 
			ans+=top;//top为 以当前节点为左端点的 有意义的子串数 
			sta[++top]=cur;
		}
	}
	
	printf("%lld\n", ans);
	
	return 0;
}