[CF 316G3]Good Substrings解题报告

#include
#include
#include
#include
using namespace std;
#define Nil NULL
typedef long long LL;
const int INF=0x7ffffff/2;
const int SIZEP=50010;
const int LNUM=11;
int M;//限制的数量
int lim_l[LNUM],lim_r[LNUM];
int match[256]={0};
class Suffix_Automaton{
public:
	class Node{
	public:
		int len;
		Node *suflink;//后缀链接
		Node *ch[26+LNUM];//转移
		int sz[LNUM];//在每个模式串中出现次数
		bool good;//是否对应"好"字符串
		int range;//对应多少个字符串
		int last;//首次出现位置
		LL suf_sz;//后缀链接能到达好节点的range之和
		void calc_range(void){
			range=len;
			if(suflink!=Nil) range-=suflink->len;
		}
		void calc_good(void){
			for(int i=1;i<=M;i++){
				if(!(lim_l[i]<=sz[i]&&sz[i]<=lim_r[i])){
					good=false;
					return;
				}
			}
			good=true;
		}
		void clear(void){
			len=0;
			suflink=Nil;
			memset(ch,0,sizeof(ch));
			memset(sz,0,sizeof(sz));
			good=false;
			range=0;
			last=-1;
			suf_sz=0;
		}
		Node(){clear();}
	};
	Node *root,*last;
	int n;
	Node *lis[1100050];
	int timer;
	int findpos(Node *a){
		if(a==Nil) return -1;
		for(int i=0;ilen<suflink)<good<last<suf_sz<sz[i]<<" ";}cout<ch[i]!=Nil){cout<<(char)('a'+i)<<" : "<ch

[i])<sz[id]=1;
		lis[n++]=cur;
		cur->len=last->len+1;
		if(id==0) cur->last=timer++;
		Node *p=last;
		while(p!=Nil&&p->ch[k]==Nil){
			p->ch[k]=cur;
			p=p->suflink;
		}
		if(p==Nil) cur->suflink=root;
		else{
			Node *q=p->ch[k];
			if(p->len+1==q->len) cur->suflink=q;
			else{
				Node *clone=new Node;
				lis[n++]=clone;
				*clone=*q;
				memset(clone->sz,0,sizeof(clone->sz));
				clone->len=p->len+1;
				cur->suflink=clone;
				q->suflink=clone;
				while(p!=Nil&&p->ch[k]==q){
					p->ch[k]=clone;
					p=p->suflink;
				}
			}
		}
		last=cur;
	}
	class cmp_len{
	public:
		bool operator () (Node *a,Node *b){
			return a->lenlen;
		}
	};
	void prepare(void){
		sort(lis,lis+n,cmp_len());
		for(int i=n-1;i>=0;i--){
			Node *p=lis[i];
			if(p->suflink!=Nil){
				for(int j=0;j<=M;j++) p->suflink->sz[j]+=p->sz[j];
				p->suflink->last=max(p->suflink->last,p->last);
			}
		}
		for(int i=0;icalc_good(),lis[i]->calc_range();
		for(int i=0;isuflink!=Nil&&p->last==p->suflink->last){
				Node *q=p->suflink;
				p->suf_sz+=q->suf_sz;
				if(q->good){
					p->suf_sz+=q->range;
				}
			}
		}
	}
	LL calc(char *s,int L){
		LL ans=0;
		Node *p=root;
		int now=0;
		for(int i=0;ich[k]==Nil){
				p=p->suflink;
				now=p->len;
			}
			if(p->ch[k]!=Nil) p=p->ch[k],now++;
			if(p->last==i){//保证不重
				ans+=p->suf_sz;
				if(p->good){
					ans+=now;
					if(p->suflink!=Nil) ans-=p->suflink->len;
				}
			}
		}
		return ans;
	}
};
Suffix_Automaton MT;
char S[SIZEP];
int L;
char str[SIZEP];
void build_MT(void){
	memset(match,-1,sizeof(match));
	for(int i=0;i<26;i++) match['a'+i]=i;
	for(int i=0;i<20;i++) match[i]=26+i;
	scanf("%s",S);
	scanf("%d",&M);
	char dlm='\0';
	L=strlen(S);
	for(int i=0;i