LCS
题目链接
VJ上的LCS
spoj上的LCS
题意
给你两个串，求两个串的最长公共字串
解题思路
大佬:
对A建后缀自动机，然后用B去匹配，若能匹配上就转移到儿子，否则沿着parent树向上跳
我的补充:
先看当下B串中新加的字符x是否能通过上次匹配的后缀来转移，如果能转移就直接加，
否则就要跳到fa树上去匹配更短endpos为p的后缀(为了找到新加入的字符x的转移)，
然后在匹配到之后就是匹配到的长度+1(要加上刚进入的x字符的一个长度)
AC代码
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
|
#include<bits/stdc++.h>
using namespace std;
const int N=250010;
char s1[N],s2[N];
int ans;
struct sam{
// 注意N是题目给的n的两倍,因为节点数最多有2*n-1个
int p,q,np,nq,cnt,last,a[N<<1][26],l[N<<1],f[N<<1];
sam(){cnt=0;last=++cnt;}
void init(){
cnt=0;last=++cnt;
memset(a,0,sizeof(a));
memset(l,0,sizeof(l));
memset(f,0,sizeof(f));
}
void extend(int c){
p=last;np=last=++cnt;l[np]=l[p]+1;
while(!a[p][c]&&p)a[p][c]=np,p=f[p];
if(!p)f[np]=1;
else{
q=a[p][c];
if(l[p]+1==l[q])f[np]=q;
else{
nq=++cnt;l[nq]=l[p]+1;
memcpy(a[nq],a[q],sizeof(a[q]));
f[nq]=f[q]; f[np]=f[q]=nq;
while(a[p][c]==q)a[p][c]=nq,p=f[p];
}
}
}
void solve(){
init();
scanf("%s",s1);scanf("%s",s2);
int n=strlen(s1);
for(int i=0;i<n;i++)extend(s1[i]-'a');
ans = 0;n=strlen(s2);
for(int i=0,p=1,tp=0;i<n;i++){
int x = s2[i] - 'a';
if(a[p][x]) tp++,p = a[p][x];
else{
for(;p&&!a[p][x];p=f[p]);
if(!p) tp=0,p=1;
else tp = l[p] + 1,p = a[p][x];
}
ans = max(ans,tp);
}
printf("%d\n",ans );
}
}sam;
int T;
int main(){
sam.solve();
return 0;
}
|
LCS2
题目链接
VJ上的LCS2
spoj上的LCS2
题意
给你多个串，求他们的最长公共字串
解题思路
超级感谢大佬的博文
大佬的想法(果然就是多种值维护一下,但是我竟然没有勇气想下去…->弱鸡下次勇敢点):
poj2774或者就是LCS那道题，对一个串建立后缀自动机，另一个在上面匹配。
(下面的方法一在代码中有详细注释，建议复制代码后结合起来看)
这道题是对多个串求。那么同样，让每个串在后缀自动机上匹配，然后记录在后缀自动机的每个节点上记录，当前串在这个位置和第一个串的最大匹配数，h数组。
然后mn数组，每次对于这所有的节点的h取小，为从第2个串到现在所有的串，都能在这个节点上匹配的长度。
因为一旦某个节点匹配上了，那么它的父节点（parent树）的父节点都会匹配上（因为父节点是当前点的后缀），
所以按拓扑倒序，更新父节点的h，为父节点的len，（即最大长度）。
第二种写法是对n-1个字符串建立SAM，然后用最后一个串在n-1个串上匹配，每个自动机上都有一个当前的指针cur，当前答案ans。对最后一个串从头开始扫，求出最后一个串和每个串以当前字符结尾的最大匹配长度，在这里面取小，每次加入一个字符，可以直接判断cur的下一位，不需要从头开始。空间太大。
总结:两种写法大同小异，只枚举举的顺序不同而已。
其实方法更简洁，更容易看懂，比解法一的缺点是多花了很多空间
方法一AC代码
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
|
// 方法一 80ms 25.6MB
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() {
int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 100010;
struct Suffix_Automaton{
int fa[N<<1], trans[N<<1][26], len[N<<1], Last, Index;
int v[N], sa[N<<1], mn[N<<1], h[N<<1];
char s[N];
void extend(int c) {
int P = Last,NP = ++Index;
len[NP] = len[P] + 1;
for (; P&&!trans[P][c]; P=fa[P]) trans[P][c] = NP;
if (!P) fa[NP] = 1; //-
else {
int Q = trans[P][c];
if (len[P] + 1 == len[Q]) fa[NP] = Q;
else {
int NQ = ++Index;
fa[NQ] = fa[Q];
len[NQ] = len[P] + 1;
memcpy(trans[NQ], trans[Q], sizeof trans[Q]);
fa[Q] = NQ;
fa[NP] = NQ;
for (; P&&trans[P][c]==Q; P=fa[P]) trans[P][c] = NQ;
}
}
Last = NP;
}
void build() {
Last = Index = 1;
scanf("%s",s+1);
int n = strlen(s+1);
for (int i=1; i<=n; ++i) extend(s[i] - 'a');
// index和第一个串s1的下标大致是对应的，但是中间还有克隆的节点
for (int i=1; i<=Index; ++i) v[len[i]] ++;
// 确实是只有n种长度..前缀的后缀-->所有的串-->所以只用n
// 这里求前缀和只是为了下面能够求出排名数组,让他们按照深度占比权值(有点像权值线段树的那种)
for (int i=1; i<=n; ++i) v[i] += v[i-1];
// sa[i] 排名为i的节点。按深度排名（拓扑用）
// i号节点按照它的len在v中前缀和减减--->其实就是排名,按照节点的长度(也就是深度)--->因为越深越长
for (int i=1; i<=Index; ++i) sa[ v[len[i]]-- ] = i;
}
void calcc() {
int n = strlen(s+1), now = 0, p = 1;
memset(h, 0, sizeof(h));
for (int i=1; i<=n; ++i) {
int c = s[i] - 'a';
if (trans[p][c]) p = trans[p][c], now ++;
else {
for (; p&&!trans[p][c]; p=fa[p]);
if (!p) now = 0, p = 1;
else now = len[p] + 1, p = trans[p][c];
}
h[p] = max(h[p], now);
}
// 拓扑倒序，parent树中从深度深的到浅的
for (int i=Index; i>=1; --i) {
int t = sa[i];
mn[t] = min(mn[t], h[t]);
// t节点有匹配,并且它的父节点(后缀link)不为源点--->那么让它的父节点的匹配值等于父节点的长度
// 因为前面的操作是对最长的适配，所以没有管较短串的匹配,所以这里管一下
// 但是为什么只对父节点，而不对更爷爷节点什么的呢，因为这个拓扑排序从底部向上，所以父节点在之后会出现
// 所以爷爷节点由后面出现的父节点去管理就行了 ====》 太精妙了，amazing！
if (h[t] && fa[t]) h[fa[t]] = len[fa[t]];
}
}
void solve() {
build();
memset(mn, 0x3f, sizeof(mn));
while (scanf("%s",s+1) != EOF) calcc();
int ans = 0;
for (int i=1; i<=Index; ++i) ans = max(ans, mn[i]);
printf("%d",ans);
}
}sam;
int main() {
sam.solve();
return 0;
}
|
方法二AC代码
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
|
// 方法二---N-1个自动机 130ms 175.1MB
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() {
int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 200010;
struct SuffixAutomaton{
int Last, Index, res, cur, fa[N], trans[N][26], len[N];
SuffixAutomaton() {Last = Index = cur = 1; res = 0;}
void extend(int c) {
int P = Last, NP = ++Index;
len[NP] = len[P] + 1;
for (; P&&!trans[P][c]; P=fa[P]) trans[P][c] = NP;
if (!P) fa[NP] = 1;
else {
int Q = trans[P][c];
if (len[P] + 1 == len[Q]) fa[NP] = Q;
else {
int NQ = ++Index;
fa[NQ] = fa[Q];
len[NQ] = len[P] + 1;
memcpy(trans[NQ], trans[Q], sizeof trans[Q]);
fa[Q] = NQ;
fa[NP] = NQ;
for (; P&&trans[P][c]==Q; P=fa[P]) trans[P][c] = NQ;
}
}
Last = NP;
}
int solve(int c) {
if (trans[cur][c]) {cur = trans[cur][c]; res++; return res;}
for (; cur&&!trans[cur][c]; cur=fa[cur]);
if (!cur) res = 0, cur = 1;
else res = len[cur] + 1, cur = trans[cur][c];
return res;
}
}sam[9];
char s[N];
char str[N>>1];
int main() {
int n = 0,t = 0,len;
scanf("%s",str+1);
while (scanf("%s",s+1)!=EOF) {
len = strlen(s + 1);
for (int i=1; i<=len; ++i)
sam[t].extend(s[i] - 'a');
t ++;
}
int ans = 0;
len = strlen(str+1);
for (int i=1; i<=len; ++i) {
int tmp = 1e9;
for (int j=0; j<t; ++j)
tmp = min(tmp, sam[j].solve(str[i] - 'a'));
ans = max(ans, tmp);
}
printf("%d",ans);
return 0;
}
|
每天一句叨叨
没有自闭，何来爆爽！向自闭的日子致敬！