str

发表于 | 更新于

Link

Solution

学了SAM总算能做这道题目了qwq。。

按照敦敦敦的论文，要保证从每个串中取出的那个子串在那个串中都是极大的。

所谓极大

设nn个字符串sis_i，从第ii个字符串选出的子串是xix_i，拼成了XX

则

用后缀自动机的话，这个思路就比较明显了。

假如后缀自动机的点pp，

说明 中的串，要是接上cc，都是满足要求的极大子串。

由此可以计数。

Code

被卡常到怀疑人生。。我都在想是不是Menci的服务器装了假的至强E5。。

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <cstdio>
#include <string>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ';
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#include <cstdlib>
#include <cstring>
#define int64 long long
enum TestLimits {
	MAXN=(int)1e6+11,
};
const int P=1e9+7;
struct SuffixAutomaton {
	struct Node {
		Node *par,*son[26];
		int rlast,rmax;
		Node(int rlast,int rmax):par(0),rlast(rlast),rmax(rmax) { memset(son,0,sizeof(son)); }
		void *operator new(size_t flag) {
			static Node *Me=(Node*)malloc((MAXN<<1)*sizeof(Node)),*Pool=Me,*temp;
			return flag?Me++:(temp=Me,Me=Pool,temp);
		}
	}*root,*last,*begin,*end;
	SuffixAutomaton(const char *s) {
		root=last=new Node(0,0);
		for(;*s;Extend(*s++));
		begin=root;
		end=(Node*)Node::operator new(0);
	}
	void Extend(char ch) {
		int x=ch-'a';
		Node *newp=new Node(last->rlast+1,last->rmax+1),*vp=last;
		for(;vp && !vp->son[x];vp->son[x]=newp,vp=vp->par);
		if(vp==0) {
			newp->par=root;
		} else {
			Node *vpx=vp->son[x];
			if(vp->rmax+1==vpx->rmax) {
				newp->par=vpx;
			} else {
				Node *o=new Node(*vpx);
				o->rmax=vp->rmax+1;
				//o->right.XXX
				vpx->par=newp->par=o;
				for(;vp && vp->son[x]==vpx;vp->son[x]=o,vp=vp->par);
			}
		}
		last=newp;
	}
};
int64 f[26];//f[x] 以x开头的合法的个数
void Deal(const char *s) {
	static int cnt[MAXN][26];
	static int64 g[26];
	SuffixAutomaton sam(s);
	--s;//下标从1开始了！！
	int n=strlen(s+1);
	for(int i=1;i<=n;++i) {
	//	memcpy(cnt[i],cnt[i-1],sizeof(cnt[0]));
		std::copy(cnt[i-1],cnt[i-1]+26,cnt[i]);
		cnt[i][s[i]-'a']++;
	}
	std::fill(g,g+26,0ll);
	for(SuffixAutomaton::Node *pos=sam.begin+1;pos!=sam.end;++pos) {
		int64 tol=1;
		for(int x=0;x<26;++x) {
			if(!pos->son[x]) {
				tol+=f[x];
			}
		}
		int *sum=cnt[pos->rlast-pos->par->rmax],*anti=cnt[pos->rlast-pos->rmax];
		for(int x=0;x<26;++x) {
			(g[x]+=tol*(sum[x]-anti[x]))%=P;
		}
	}
	for(int x=0;x<26;++x) {
		if(!sam.root->son[x]) {
			(g[x]+=f[x])%=P;
		}
	}
	std::copy(g,g+26,f);
}
int main() {
	static char *str[MAXN],_strPool[MAXN<<1],*strPool=_strPool;
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		str[i]=strPool;
		is>>str[i];
		for(;*strPool;++strPool);
		++strPool;
	}
	for(int i=n;i>=1;--i) {
		Deal(str[i]);
	}
	int64 Ans=1;
	for(int x=0;x<26;++x) {
		Ans+=f[x];
	}
	Ans%=P;
	os<<Ans<<'\n';
	return 0;
}