Reku
0%

后缀自动机

Posted on Edited on In Views: Valine:

我们都知道后缀自动机的构造是比较难以理解的，所以我想先知道后缀自动机构建出来的东西是什么。 首先后缀自动机构造出来的一定是一个自动机，这个自动机可以接收一个字符串所有的后缀，显然这个自动机是一个DAG图。 然后这个自动机的每个状态代表什么呢？代表结束位置相同的子串，比如ab和aab在aabaab中都在\(3,6\)位置结尾，那么这两个串可以认为在后缀自动机中是同一个状态。 后缀自动机大概维护这么几个东西：

\(MAXLEN[ST]\) : \(ST\)对应的最长的字符串

\(MINLEN[ST]\) : \(ST\)对应的最短的字符串

\(TRANS[ST][]\) : \(ST\)对应的转移函数

\(SLINK[ST]\) : \(ST\)对应的最小的超集，比如\((3,6,9)\)是\((3,6)\)的超集。

\(SLINK\)指向的状态一定是当前状态的一个前缀，而且形成的一定是一棵树

\(ENDPOS[ST]\) : \(ST\)状态包含的子串的结束位置个数，可以通过\(SLINK\)树自底向上来求出

至于这个后缀自动机的构造方法，就抄个板子？

http://hihocoder.com/problemset/problem/1445

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。 现在小Hi想知道一部作品中出现了多少不同的旋律？

这个不同旋律出现的次数，对于每个状态，不同的子串个数为\(maxlen-minlen+1\)，然后对每个状态算一算就好了。

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
#include<bits/stdc++.h>
const int MAXL = 1000000;
char s[MAXL + 10];
int n = 0, len, st;
int maxlen[2 * MAXL + 10], minlen[2 * MAXL + 10], trans[2 * MAXL + 10][26], slink[2 * MAXL + 10];

int new_state(int _maxlen, int _minlen, int* _trans, int _slink) {
        maxlen[n] = _maxlen;
        minlen[n] = _minlen;
        for(int i = 0; i < 26; i++) {
                if(_trans == NULL)
                        trans[n][i] = -1;
                else
                        trans[n][i] = _trans[i];
        }
        slink[n] = _slink;
        return n++;
}

int add_char(char ch, int u) {
        int c = ch - 'a';
        int z = new_state(maxlen[u] + 1, -1, NULL, -1);
        int v = u;
        while(v != -1 && trans[v][c] == -1) {
                trans[v][c] = z;
                v = slink[v];
        }
        if(v == -1) { //最简单的情况，suffix-path(u->S)上都没有对应字符ch的转移
                minlen[z] = 1;
                slink[z] = 0;
                return z;
        }
        int x = trans[v][c];
        if(maxlen[v] + 1 == maxlen[x]) { //较简单的情况，不用拆分x
                minlen[z] = maxlen[x] + 1;
                slink[z] = x;
                return z;
        }
        int y = new_state(maxlen[v] + 1, -1, trans[x], slink[x]); //最复杂的情况，拆分x
        slink[y] = slink[x];
        minlen[x] = maxlen[y] + 1;
        slink[x] = y;
        minlen[z] = maxlen[y] + 1;
        slink[z] = y;
        int w = v;
        while(w != -1 && trans[w][c] == x) {
                trans[w][c] = y;
                w = slink[w];
        }
        minlen[y] = maxlen[slink[y]] + 1;
        return z;
}

int main()
{
	scanf("%s",s+1);
	len=strlen(s+1);
	st=new_state(0,0,NULL,-1);
	for(int i=1;i<=len;i++)
	{
		st=add_char(s[i],st);
	}
	long long ans=0;
	for(int i=1;i<n;i++)
	{
		ans+=maxlen[i]-minlen[i]+1;
	}
	printf("%lld\n",ans);
	return 0;
}

http://hihocoder.com/problemset/problem/1449

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。 现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。

通过\(slink\)树，我们可以构建出每个状态的结束位置个数，这样的话就知道了每个\(maxlen\)出现了多少次，因为最后的答案一定是按照长度单调递减的，所以就维护一个类似于前缀最大值就好了。

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
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6;
const int M = 26;

struct state {
  int maxlen, minlen, slink;
  int trans[M];
};

state st[N * 2 + 10];
int degree[N * 2 + 10];
int endpos[N * 2 + 10];
bool prefix[N * 2 + 10];

char s[N + 10];
int size, last;

int new_state(int maxlen, int minlen, int slink, int *trans) {
  prefix[size] = false;
  degree[size] = 0;
  endpos[size] = 0;
  st[size].maxlen = maxlen;
  st[size].minlen = minlen;
  st[size].slink = slink;
  for (int i = 0; i < M; i++) {
    if (trans == NULL)
      st[size].trans[i] = -1;
    else
      st[size].trans[i] = trans[i];
  }
  return size++;
}

int add_char(char ch, int u) {
  int c = ch - 'a', v, x, y;
  int cur = new_state(st[u].maxlen + 1, -1, -1, NULL);
  prefix[cur] = true;
  endpos[cur] = 1;
  
  for (v = u; v != -1 && st[v].trans[c] == -1; v = st[v].slink) {
    st[v].trans[c] = cur;
  }
  if (v == -1) {
    st[cur].minlen = 1;
    st[cur].slink = 0;
    degree[0]++;
    return cur;
  }
  x = st[v].trans[c];
  if (st[v].maxlen + 1 == st[x].maxlen) {
    st[cur].minlen = st[x].maxlen + 1;
    st[cur].slink = x;
    degree[x]++;
    return cur;
  }

  y = new_state(st[v].maxlen + 1, -1, st[x].slink, st[x].trans);
  for (int w = v; w != -1 && st[w].trans[c] == x; w = st[w].slink)
    st[w].trans[c] = y;
  st[x].slink = st[cur].slink = y;
  degree[y] += 2;
  st[x].minlen = st[cur].minlen = st[y].maxlen + 1;
  st[y].minlen = st[st[y].slink].maxlen + 1;

  return cur;
}

void topo() {
  queue<int> q;
  for (int i = 1; i < size; i++) {
    if (degree[i] == 0)
      q.push(i);
  }
  while (!q.empty()){
    int x = q.front(); q.pop();
    endpos[st[x].slink] += endpos[x];
    if (--degree[st[x].slink] == 0)
      q.push(st[x].slink);
  }
}

void init() {
  size = 0;
  last = new_state(0, 0, -1, NULL);
}

int ans[N + 10];

int main()
{
	scanf("%s",s+1);
	int len=strlen(s+1);
	init();
	for(int i=1;i<=len;i++)
	{
		last=add_char(s[i],last);
	}
	topo();
	for(int i=0;i<size;i++)
	{
		ans[st[i].maxlen]=max(ans[st[i].maxlen],endpos[i]);
	}
	for(int i=len-1;i>=1;i--)
	{
		ans[i]=max(ans[i],ans[i+1]);
	}
	for(int i=1;i<=len;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

http://hihocoder.com/problemset/problem/1457

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。 神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集，顾名思义，这部作品集里有许多作品，但是所有的作品有一个共同特征：只用了十个音符，所有的音符都表示成0-9的数字。 现在小Hi想知道这部作品中所有不同的旋律的“和”（也就是把串看成数字，在十进制下的求和，允许有前导0）。答案有可能很大，我们需要对（10^9 + 7)取摸。

用像后缀数组处理多串的方法，把所有的串都串起来，然后在DAG跑个DP套DP就好了。

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h>

using namespace std;

const int N = 2e6;
const int M = 11;
const long long mod = 1e9+7;

struct state {
  int maxlen, minlen, slink;
  int trans[M];
};

state st[N * 2 + 10];
int degree[N * 2 + 10];
int endpos[N * 2 + 10];
bool prefix[N * 2 + 10];
int indegree[N * 2 + 10];
long long valad[N * 2 + 10];
long long ans[N * 2 + 10];
long long sum;
char s[N + 10];
char c[N + 10];
int size, last;

int new_state(int maxlen, int minlen, int slink, int *trans) {
  prefix[size] = false;
  degree[size] = 0;
  endpos[size] = 0;
  st[size].maxlen = maxlen;
  st[size].minlen = minlen;
  st[size].slink = slink;
  for (int i = 0; i < M; i++) {
    if (trans == NULL)
      st[size].trans[i] = -1;
    else
      st[size].trans[i] = trans[i];
  }
  return size++;
}

int add_char(char ch, int u) {
  int c = ch - '0', v, x, y;
  int cur = new_state(st[u].maxlen + 1, -1, -1, NULL);
  prefix[cur] = true;
  endpos[cur] = 1;
  
  for (v = u; v != -1 && st[v].trans[c] == -1; v = st[v].slink) {
    st[v].trans[c] = cur;
  }
  if (v == -1) {
    st[cur].minlen = 1;
    st[cur].slink = 0;
    degree[0]++;
    return cur;
  }
  x = st[v].trans[c];
  if (st[v].maxlen + 1 == st[x].maxlen) {
    st[cur].minlen = st[x].maxlen + 1;
    st[cur].slink = x;
    degree[x]++;
    return cur;
  }

  y = new_state(st[v].maxlen + 1, -1, st[x].slink, st[x].trans);
  for (int w = v; w != -1 && st[w].trans[c] == x; w = st[w].slink)
    st[w].trans[c] = y;
  st[x].slink = st[cur].slink = y;
  degree[y] += 2;
  st[x].minlen = st[cur].minlen = st[y].maxlen + 1;
  st[y].minlen = st[st[y].slink].maxlen + 1;

  return cur;
}

void topo() {
  queue<int> q;
  for (int i = 1; i < size; i++) {
    if (degree[i] == 0)
      q.push(i);
  }
  while (!q.empty()){
    int x = q.front(); q.pop();
    endpos[st[x].slink] += endpos[x];
    if (--degree[st[x].slink] == 0)
      q.push(st[x].slink);
  }
}

void init() {
  size = 0;
  last = new_state(0, 0, -1, NULL);
  valad[0] = 1;
}

int n;

int main()
{
	scanf("%d",&n);
	int len=0;
	init();
	for(int i=1;i<=n;i++)
	{
		scanf("%s",c+1);
		int ll=strlen(c+1);
		if(len!=0)
		{
			len++;
			s[len]='0'+10;
		}
		for(int j=1;j<=ll;j++)
		{
			len++;
			s[len]=c[j];
		}
	}
	for(int i=1;i<=len;i++)
	{
		last=add_char(s[i],last);
	}
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(st[i].trans[j]!=-1)
			{
				indegree[st[i].trans[j]]++;
			}
		}
	}
	queue<int> q;
	q.push(0);
	while(!q.empty())
	{
		int t=q.front();
		sum=(ans[t]+sum)%mod;
		q.pop();
		for(int i=0;i<M;i++)
		{
			int v=st[t].trans[i];
			if(v==-1) continue;
			if(i!=10)
			{
				valad[v]=(valad[v]+valad[t])%mod;
				ans[v]=(ans[v]+ans[t]*10+i*valad[t])%mod;
			}
			indegree[v]--;
			if(indegree[v]==0)
			{
				q.push(v);
			}
		}
	}
	printf("%lld\n",sum);
	return 0;
}

http://hihocoder.com/problemset/problem/1465

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。 小Hi发现旋律可以循环，每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”，还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。 小Hi对此产生了浓厚的兴趣，他有若干段旋律，和一部音乐作品。对于每一段旋律，他想知道有多少在音乐作品中的子串（重复便多次计）和该旋律是“循环相似旋律”。

对于循环同构的一个处理方法就是把字符串翻倍，然后看看最长公共子串是不是大于\(N\)，问题就是怎么求这个最长公共子串。 我们用类似kmp的方法处理，然后用endpos记一下数，就好了。

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6;
const int M = 26;
const long long mod = 1e9+7;

struct state {
  int maxlen, minlen, slink;
  int trans[M];
};

state st[N * 2 + 10];
int degree[N * 2 + 10];
int endpos[N * 2 + 10];
bool prefix[N * 2 + 10];
bool vis[N * 2 + 10];
char s[N + 10];
char t[N + 10];
int size, last;

int new_state(int maxlen, int minlen, int slink, int *trans) {
  prefix[size] = false;
  degree[size] = 0;
  endpos[size] = 0;
  st[size].maxlen = maxlen;
  st[size].minlen = minlen;
  st[size].slink = slink;
  for (int i = 0; i < M; i++) {
    if (trans == NULL)
      st[size].trans[i] = -1;
    else
      st[size].trans[i] = trans[i];
  }
  return size++;
}

int add_char(char ch, int u) {
  int c = ch - 'a', v, x, y;
  int cur = new_state(st[u].maxlen + 1, -1, -1, NULL);
  prefix[cur] = true;
  endpos[cur] = 1;
  
  for (v = u; v != -1 && st[v].trans[c] == -1; v = st[v].slink) {
    st[v].trans[c] = cur;
  }
  if (v == -1) {
    st[cur].minlen = 1;
    st[cur].slink = 0;
    degree[0]++;
    return cur;
  }
  x = st[v].trans[c];
  if (st[v].maxlen + 1 == st[x].maxlen) {
    st[cur].minlen = st[x].maxlen + 1;
    st[cur].slink = x;
    degree[x]++;
    return cur;
  }

  y = new_state(st[v].maxlen + 1, -1, st[x].slink, st[x].trans);
  for (int w = v; w != -1 && st[w].trans[c] == x; w = st[w].slink)
    st[w].trans[c] = y;
  st[x].slink = st[cur].slink = y;
  degree[y] += 2;
  st[x].minlen = st[cur].minlen = st[y].maxlen + 1;
  st[y].minlen = st[st[y].slink].maxlen + 1;

  return cur;
}

void topo() {
  queue<int> q;
  for (int i = 1; i < size; i++) {
    if (degree[i] == 0)
      q.push(i);
  }
  while (!q.empty()){
    int x = q.front(); q.pop();
    endpos[st[x].slink] += endpos[x];
    if (--degree[st[x].slink] == 0)
      q.push(st[x].slink);
  }
}

void init() {
  size = 0;
  last = new_state(0, 0, -1, NULL);
}

int ff()
{
	scanf("%s",t+1);
	int len=strlen(t+1);
	for(int i=0;i<size;i++)
	{
		vis[i]=0;
	}
	for(int i=1;i<=len;i++)
	{
		t[len+i]=t[i];
	}
	len*=2;
	int u,l;
	u=l=0;
	int ans=0;
	for(int i=1;i<=len;i++)
	{
		int v=t[i]-'a';
		while(u!=0 && st[u].trans[v]==-1)
		{
			u=st[u].slink;
			l=st[u].maxlen;
		}
		if(st[u].trans[v]!=-1)
		{
			u=st[u].trans[v];
			l++;
		}
		else
		{
			u=l=0;
		}
		if(l>len/2)
		{
			while(st[st[u].slink].maxlen>=len/2)
			{
				u=st[u].slink;
				l=st[u].maxlen;
			}
		}
		if(l>=len/2 && vis[u]==0)
		{
			vis[u]=1;
			ans+=endpos[u];
		}
	}
	return ans;
}

int n;

int main()
{
	scanf("%s",s+1);
	int len = strlen(s+1);
	init();
	for(int i = 1; i <= len; i++)
	{
		last = add_char(s[i],last);
	}
	topo();
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
	{
		printf("%d\n",ff());
	}
	return 0;
}