HDU-4416_题解

发表于 | 分类于 |

依次模拟最长公共子串的匹配过程，每到一个状态，标记最长不可用后缀的长度countAns。全部跑完后，树形dp更新祖先的countAns，因为祖先是后缀，长度小于子孙的匹配部分的子串也不可用了。最后累加可用部分的数量得到答案。 

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
/*
 *powered by caibiCH2
 *create at 2019-11-10 20:44:12
 */
#include <bits/stdc++.h>
#define elif else if
//#define max(x,y) ((x)>(y)?(x):(y))
//#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;

typedef unsigned pnt;
const char ori='a',fin='z';
const pnt csize=fin-ori+1;
const int maxn=110000;
struct SAM{

	struct node{
		ll len,countAns;
		pnt next[csize],fa;
		int cnt,firstpos;
	}data[maxn<<1];
	pnt l;
	void init(){
		memset(this,0,sizeof(*this));
	}
	
	void build(const string&s){
		pnt lst=0;
		data[0].fa=-1;
		for(int i=0;i<s.length();++i){
			char c=s[i]-ori;
			
			data[++l].len=data[lst].len+1;
			pnt p=lst;lst=l;data[l].cnt=1;data[l].firstpos=data[l].len-1;
			for(;(~p)&&!data[p].next[c];p=data[p].fa)data[p].next[c]=l;
			if(!~p)data[l].fa=0;
			else{
				pnt q=data[p].next[c];
				if(data[q].len==data[p].len+1)data[l].fa=q;
				else{
					data[++l]=data[q];data[l].cnt=0;
					data[l].len=data[p].len+1;
					data[q].fa=data[l-1].fa=l;
					for(;(~p)&&data[p].next[c]==q;p=data[p].fa)data[p].next[c]=l;
				}
			}
		}
//		buildCnt();
	}
	
	pnt find(const string&s){
		pnt now=0;
		for(pnt i=0;i<s.length();++i){
			if(!data[now].next[s[i]-ori])return 0;
			now=data[now].next[s[i]-ori];
		}
		return now;
	}
	
	void run(const string&s){
		pnt now=0;ll maxlen=0;
		for(int i=0;i<s.size();i+=1){
			while(now&&!data[now].next[s[i]-ori])now=data[now].fa,maxlen=data[now].len;
			now=data[now].next[s[i]-ori];
			if(now){
				++maxlen;
				data[now].countAns=max(data[now].countAns,maxlen);
			}
		}
	}
	
	ll count(){
		vector<int>a(l+1),b(l+1);
		for(int i=0;i<=l;i+=1)++a[data[i].len];
		for(int i=1;i<=l;i+=1)a[i]+=a[i-1];
		for(int i=0;i<=l;i+=1)b[--a[data[i].len]]=i;
		for(int i=l;i;--i){
			data[data[b[i]].fa].countAns= max(data[b[i]].countAns,data[data[b[i]].fa].countAns);
		}
		ll ans=0;
		for(int i=1;i<=l;i+=1){
			ans+=max(0ll,data[b[i]].len-max(data[data[b[i]].fa].len,data[b[i]].countAns));
		}
		return ans;
	}
	
//    void buildCnt(){
//		vector<int>a(l+1),b(l+1);
//		for(int i=0;i<=l;i+=1)++a[data[i].len];
//		for(int i=1;i<=l;i+=1)a[i]+=a[i-1];
//		for(int i=0;i<=l;i+=1)b[--a[data[i].len]]=i;
//		
//		for(int i=l;i;--i){
//			data[data[b[i]].fa].cnt+=data[b[i]].cnt;
//		}
//        data[0].cnt=0;
//    }
	void print(){
		cout<<"Next DAG:"<<endl;
		for(int i=0;i<=l;i+=1){
			cout<<i<<":";
			for(char c=0;c<csize;c+=1){
				if(data[i].next[c])cout<<char(ori+c)<<":"<<data[i].next[c]<<' ';
			}
			cout<<endl;
		}
		cout<<"parent tree:"<<endl;
		for(int i=1;i<=l;i+=1){
			cout<<i<<':'<<data[i].fa<<' ';
		}
		cout<<endl;
		cout<<"cnt:"<<endl;
		for(int i=1;i<=l;i+=1){
			cout<<i<<':'<<data[i].cnt<<' ';
		}
	}
	
}dag;

int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
//	std::cin.tie(0);
	int T;cin>>T;
	for(int o=1;o<=T;o+=1){
		dag.init();
		int n;cin>>n;string s;cin>>s;dag.build(s);
		for(int i=1;i<=n;i+=1){
			string t;cin>>t;
			dag.run(t);
		}
		cout<<"Case "<<o<<": "<<dag.count()<<'\n';
//		cout<<dag.check()<<'\n';
	}
	return 0;
}