列表

详情

NC205333. WordsFascinating

描述

As we all know the fact, you can use several Source Words to compose an Interesting Word. Little Gyro has already learnt this fantastic idea from one of his best friends Brother Yu.
On Little Gryo's birthday, fortunately, Little Gryo received a gift from Brother Yu. The gift consists of n Interesting Words S_1, S_2,..., S_n. Little Gyro also thought those words were really fantastic. So he decided to play with these words.
For each Interesting Word S_i, Little Gyro will select a period of consecutive letters P_i, and splice into a new word T within the given order, and then he defined these kind of words "Fascinating Words". It means you can take apart a Fascinating Word T and form n period of consecutive letters from the given Interesting Words. Specially, if Little Gyro considers the Interesting Word really useless, he'll not choose any letter from this Interesting Word either.
For example, supposed that there are some Interesting Words: "telephone", "microscope". Little Gyro may select a period of consecutive letters from each given word such as: "tele", "scope". And then form the Fascinating Word "telescope". Specially, Little Gyro also can only select "scope" and form the Fascinating Word "scope", if he dislikes the first Interesting Word.
Now given all the Interesting Words that Little Gyro has received on his birthday, Little Gyro wants to know the total number of the different Fascinating Words that he can generate.

输入描述

Each input file only contains one test case.
The first line contains an integer n (1 ≤ n ≤ 2000), indicating the number of the Interesting Words.
Then, the following n lines, each line contains an Interesting Word S_i (1 ≤  ≤ 5×).
It's guaranteed that the Interesting Words can only be made up by the lowercase letters, and the sum of the length of the Interesting Words S_i of all test cases will not exceed 5×.

输出描述

For each test case, output the number of the different Fascinating Words that Little Gyro can generate.
Because the number may be very large, just output the number mod .

示例1

输入: 

2
aa
ab

输出: 

8

示例2

输入: 

3
abb
aca
aba

输出: 

139

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 48ms, 内存消耗: 40168K, 提交时间: 2020-06-06 14:55:54 

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const double pi=acos(-1.0);
const double eps=1e-10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
int n,las,tot,top;
string s[maxn];
int dp[maxn<<1],rt[maxn],buf[26];
struct node{
	int ch[26];
	int fa,len;
}a[maxn<<1];
void add(int c){
	int p=las,np=las=++tot;
	a[np].len=a[p].len+1;
	for(;p&&!a[p].ch[c];p=a[p].fa)a[p].ch[c]=np;
	if(!p)a[np].fa=top;
	else{
		int q=a[p].ch[c];
		if(a[q].len==a[p].len+1)a[np].fa=q;
		else{
			int nq=++tot;a[nq]=a[q];
			a[nq].len=a[p].len+1;
			a[np].fa=a[q].fa=nq;
			for(;p&&a[p].ch[c]==q;p=a[p].fa)a[p].ch[c]=nq;
		}
	}
}
int dfs(int u){
	if(dp[u])return dp[u];
	dp[u]=1;
	for(int i=0;i<26;i++){
		if(a[u].ch[i]){
			dp[u]=(dp[u]+dfs(a[u].ch[i]))%mod;
		}
	}
	return dp[u];
}
int main(void){
//	freopen("str1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	tot=0;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		top=rt[i]=las=++tot;
		for(int j=0;j<s[i].length();j++)add(s[i][j]-'a');
	}
	rt[n+1]=++tot;
	for(int i=n;i>=1;i--){
		for(int j=rt[i];j<rt[i+1];j++){
			for(int k=0;k<26;k++){
				if(!a[j].ch[k])a[j].ch[k]=buf[k];
			}
		}
		for(int k=0;k<26;k++){
			buf[k]=a[rt[i]].ch[k];
		}
	}
	cout<<dfs(1)<<endl;
	return 0;
}

上一题

© 2024 nowcoder.com