#1445 : 后缀自动机二·重复旋律5
时间限制:10000ms
单点时限:2000ms
内存限制:256MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中出现了多少不同的旋律？
输入
共一行，包含一个由小写字母构成的字符串。字符串长度不超过 1000000。
输出
一行一个整数，表示答案。
- 样例输入
-
aab
- 样例输出
-
5
后缀自动机，学习了最短路的转移。
/*************************************************************************
> File: main.cpp
> Author: You Siki
> Mail: You.Siki@outlook.com
> Time: 2016年12月23日 星期五 14时25分55秒
************************************************************************/ #include<bits/stdc++.h> //using namespace std; const int maxn = ; /* AUTOMATON */ int last = ;
int tail = ;
int step[maxn];
int fail[maxn];
int mini[maxn];
int next[maxn][]; inline void buildAutomaton(char *s)
{
while (*s)
{
int p = last;
int t = tail++;
int c = *s++ - 'a';
step[t] = step[p] + ;
while (p && !next[p][c])
next[p][c] = t, p = fail[p];
if (p)
{
int q = next[p][c];
if (step[q] == step[p] + )
fail[t] = q, mini[t] = step[q] + ;
else
{
int k = tail++;
fail[k] = fail[q];
fail[q] = fail[t] = k;
step[k] = step[p] + ;
mini[q] = step[k] + ;
mini[t] = step[k] + ;
for (int i = ; i < ; ++i)
next[k][i] = next[q][i];
while (p && next[p][c] == q)
next[p][c] = k, p = fail[p];
mini[k] = step[fail[k]] + ;
}
}
else
fail[t] = , mini[t] = ;
last = t;
}
} inline long long solve(void)
{
long long ret = ;
for (int i = ; i < tail; ++i)
ret += step[i] - mini[i] + ;
return ret;
} /* MAIN FUNC */ char str[maxn]; signed main(void)
{
scanf("%s", str);
buildAutomaton(str);
printf("%lld\n", solve());
}
20170222 复习SAM模板
#include <cstdio>
#include <cstring> const int siz = ; int last = ;
int tail = ;
int mini[siz];
int maxi[siz];
int fail[siz];
int next[siz][]; inline void build(char *s)
{
while (*s)
{
int p = last;
int t = tail++;
int c = *s++ - 'a'; maxi[t] = maxi[p] + ; while (p && !next[p][c])
next[p][c] = t, p = fail[p]; if (p)
{
int q = next[p][c]; if (maxi[q] == maxi[p] + )
fail[t] = q, mini[t] = maxi[q] + ;
else
{
int k = tail++; fail[k] = fail[q];
fail[t] = fail[q] = k;
maxi[k] = maxi[p] + ;
mini[q] = maxi[k] + ;
mini[t] = maxi[k] + ;
mini[k] = maxi[fail[k]] + ; memcpy(next[k], next[q], * sizeof(int)); while (next[p][c] == q)
next[p][c] = k, p = fail[p];
}
}
else
fail[t] = , mini[t] = ; last = t;
}
} inline void calc(void)
{
long long ans = ; for (int i = ; i < tail; ++i)
ans += maxi[i] - mini[i] + ; printf("%lld\n", ans);
} signed main(void)
{
static char s[siz]; scanf("%s", s); build(s); calc();
}
@Author: YouSiki