#include <bits/stdc++.h>
using namespace std;
const int maxn = 7e5 + 10;
struct tree
{
int fail, end;
int vis[26];
} AC[maxn];
int cnt;
int v[maxn];
inline void build(string s, int num)
{
int l = s.length();
int now = 0;
for (int i = 0; i < l; i++)
{
if (AC[now].vis[s[i] - 'a'] == 0)
{
AC[now].vis[s[i] - 'a'] = ++cnt;
}
now = AC[now].vis[s[i] - 'a'];
}
AC[now].end++;
}
void get_fail()
{
queue<int> q;
for (int i = 0; i < 26; i++)
{
if (AC[0].vis[i] != 0)
{
AC[AC[0].vis[i]].fail = 0;
q.push(AC[0].vis[i]);
}
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (AC[u].vis[i] != 0)
{
AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
q.push(AC[u].vis[i]);
}
else
{
AC[u].vis[i] = AC[AC[u].fail].vis[i];
}
}
}
}
void solve()
{
int n;
cin >> n;
cnt = 0;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
build(s, i);
}
for (int i = 1; i <= n; i++)
{
v[i] = 0;
}
string s;
cin >> s;
get_fail();
int now = 0;
int tot = 0;
for (int i = 0; i < s.length(); i++)
{
now = AC[now].vis[s[i] - 'a'];
for (int x = now; x; x = AC[x].fail)
{
if (AC[x].end != 0)
{
tot += AC[x].end;
AC[x].end = 0;
}
}
}
for (int i = 0; i <= cnt; i++)
{
for (int j = 0; j < 26; j++)
AC[i].vis[j] = 0;
AC[i].end = 0;
AC[i].fail = 0;
}
cout << tot << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
活动打卡代码
AcWing 1282. 搜索关键词
活动打卡代码
AcWing 4821. 拓展回文
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int maxn = 1e5 + 10;
const int N = 1e5 + 10;
string s;
ull base = 131;
int n;
const int mod = 1610612741, mdd = 805306457, mddd = 402653189; // mod:垃圾模数
ull p[N];
ull has1[N], has2[N];
void get_hash()
{
p[0] = 1;
has1[0] = 1, has2[0] = 1;
for (int i = 1; i <= n; i++)
{ // 正的hash
p[i] = p[i - 1] * base % mod;
has1[i] = (has1[i - 1] * base % mod + (s[i] - 'a')) % mod;
}
for (int i = n; i >= 1; i--)
{ // 翻转的hash
has2[i] = (has2[i + 1] * base % mod + (s[i] - 'a')) % mod;
}
}
int get1(int l, int r)
{
if (l > r)
return -1;
return (has1[r] - has1[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
int get2(int l, int r)
{
if (l > r)
return -1;
return (has2[l] - has2[r + 1] * p[r - l + 1] % mod + mod) % mod;
}
void solve()
{
n = s.length();
s = ' ' + s;
get_hash();
int ans = n;
pair<int, int> pos = {n, 0};
for (int i = (n) / 2; i <= n; i++)
{
int len1 = i;
int len2 = n - i;
len1--; // 以i为中心
if (len1 >= len2)
{
if (get1(i + 1, n) == get2(i - 1 - len2 + 1, i - 1))
{
if (ans > len1 - len2)
{
ans = len1 - len2;
pos.first = i;
pos.second = 1;
}
}
}
len1++;
if (len1 >= len2)
{
if (get1(i + 1, n) == get2(i - len2 + 1, i))
{
if (ans > len1 - len2)
{
ans = len1 - len2;
pos.first = i;
pos.second = 0;
}
}
}
}
if (pos.second == 0)
{
string s2;
for (int i = 1; i <= pos.first; i++)
{
s2.push_back(s[i]);
cout << s[i];
}
for (int i = pos.first; i >= 1; i--)
cout << s2[i - 1];
cout << endl;
}
else
{
string s2;
pos.first--;
for (int i = 1; i <= pos.first; i++)
{
s2.push_back(s[i]);
cout << s[i];
}
cout << s[pos.first + 1];
for (int i = pos.first; i >= 1; i--)
cout << s2[i - 1];
cout << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> s)
solve();
}
活动打卡代码
AcWing 4778. 短语
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
int s[maxn];
int sa[maxn], rk[maxn], ht[maxn];
void buildsa(int *s, int *sa, int *rk, int *ht, int n, int m = 128) // nlogn
{
static int x[maxn], y[maxn], c[maxn];
s[n] = 0; //*用来处理溢出问题
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
for (int j = 0; j <= n; j++)
swap(x[j], y[j]);
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]);
k = max(k - 1, 0ll);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while ((i + k < n && j + k < n) && s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
struct node
{
int c[11][2];
} e[maxn];
int ct;
int pos = 0;
int col[maxn];
int L[11], R[11];
bool check(int x)
{
int cnt = 0;
for (int i = 1; i < pos; i++)
{
if (ht[i] >= x && (ht[i - 1] >= x))
{
if (s[sa[i]] < 50)
{
e[cnt].c[col[sa[i]]][0] = min(e[cnt].c[col[sa[i]]][0], sa[i]);
e[cnt].c[col[sa[i]]][1] = max(e[cnt].c[col[sa[i]]][1], sa[i]);
}
}
else if (ht[i] >= x && (i == 1 || ht[i - 1] < x))
{
++cnt;
for (int j = 1; j <= ct; j++)
{
e[cnt].c[j][0] = 1e18, e[cnt].c[j][1] = 0;
}
if (s[sa[i]] < 50)
{
e[cnt].c[col[sa[i]]][0] = sa[i];
e[cnt].c[col[sa[i]]][1] = sa[i];
}
if (s[sa[i - 1]] < 50)
{
e[cnt].c[col[sa[i - 1]]][0] = min(e[cnt].c[col[sa[i - 1]]][0], sa[i - 1]);
e[cnt].c[col[sa[i - 1]]][1] = max(e[cnt].c[col[sa[i - 1]]][1], sa[i - 1]);
}
}
}
for (int i = 1; i <= cnt; i++)
{
// cout << i << endl;
int ok = 1;
for (int j = 1; j <= ct; j++)
{
// cout << e[i].c[j][0] << ' ' << e[i].c[j][1] << endl;
if (e[i].c[j][0] >= e[i].c[j][1])
ok = 0;
else
{
if (e[i].c[j][1] - e[i].c[j][0] >= x)
{
}
else
ok = 0;
}
}
if (ok == 1)
return 1;
}
return 0;
}
void solve()
{
cin >> ct;
int maxcnt = 1e18;
pos = 0;
for (int i = 1; i <= ct; i++)
{
L[i] = pos;
string s1;
cin >> s1;
for (int j = pos; j < pos + s1.length(); j++)
{
s[j] = s1[j - pos] - 'a';
}
int l = s1.length();
maxcnt = min(maxcnt, 1ll * l);
pos += s1.length();
R[i] = pos - 1;
s[pos++] = 50 + i;
// cout << L[i] << ' ' << R[i] << endl;
}
// cout << pos << endl;
buildsa(s, sa, rk, ht, pos);
int l = 1, r = maxcnt;
for (int i = 1; i <= ct; i++)
{
// cout << i << endl;
for (int j = L[i]; j <= R[i]; j++)
{
// cout << rk[j] << ' ';
col[j] = i;
}
// cout << endl;
}
// cout << check(2);
// return;
int ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
活动打卡代码
AcWing 4686. 子串
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int sa[maxn], ht[maxn];
int s[maxn];
int rk[maxn];
int x[maxn], y[maxn], c[maxn];
void buildsa(int *s, int *sa, int *rk, int *ht, int n, int m = 500) // nlogn
{
s[n] = 0; //*用来处理溢出问题
for (register int i = 0; i < m; i++)
c[i] = 0;
for (register int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (register int i = 1; i < m; i++)
c[i] += c[i - 1];
for (register int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
for (int j = 0; j <= n; j++)
{
swap(x[j], y[j]);
}
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]); 取1-n-1
k = max(k - 1, 0);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
struct node
{
int l, r;
int ct[101];
int tot;
} e[maxn];
int n;
int ans;
int L[maxn], R[maxn];
int len1 = 0;
int col[maxn];
bool check(int x)
{
int cnt = 0;
for (int i = 1; i < len1; i++)
{
for (int j = 1; j <= n; j++)
e[i].ct[j] = 0;
e[i].tot = 0;
}
for (int i = 1; i < len1; i++)
{
if (ht[i] >= x && (ht[i - 1] >= x))
{
e[cnt].r = i;
if (s[sa[i]] < 200)
{
e[cnt].ct[col[sa[i]]]++;
if (e[cnt].ct[col[sa[i]]] == 1)
{
e[cnt].tot++;
}
}
}
else if (ht[i] >= x && (i == 1 || ht[i - 1] < x))
{
e[++cnt].l = i, e[cnt].r = i;
if (s[sa[i]] < 200)
{
e[cnt].ct[col[sa[i]]]++;
if (e[cnt].ct[col[sa[i]]] == 1)
{
e[cnt].tot++;
}
}
if (s[sa[i - 1]] < 200)
{
e[cnt].ct[col[sa[i - 1]]]++;
if (e[cnt].ct[col[sa[i - 1]]] == 1)
{
e[cnt].tot++;
}
}
}
}
for (int i = 1; i <= cnt; i++)
{
if (e[i].tot == n)
{
return 1;
}
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n;
int pos = 0;
for (int i = 1; i <= n; i++)
{
L[i] = pos;
string s3;
cin >> s3;
for (int j = pos; j < s3.length() + pos; j++)
{
s[j] = s3[j - pos] - 'A' + 1;
}
pos += s3.length();
s[pos++] = 200 + i;
for (int j = 0; j < s3.length() / 2; j++)
{
swap(s3[j], s3[s3.length() - 1 - j]);
}
for (int j = pos; j < s3.length() + pos; j++)
{
s[j] = s3[j - pos] - 'A' + 1;
}
pos += s3.length();
R[i] = pos - 1;
s[pos++] = 200 + i + n;
}
len1 = pos;
buildsa(s, sa, rk, ht, len1);
int l = 1, r = 100;
for (int i = 1; i <= n; i++)
{
// cout << i << endl;
for (int j = L[i]; j <= R[i]; j++)
{
col[j] = i;
}
}
int ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
{
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
cout << ans << endl;
}
}
/*
2
ABCD
Abcd
*/
活动打卡代码
AcWing 4775. 长信息
#include<iostream>
#include<set>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
#define int long long
const int maxn = 2e6 + 10;
int sa[maxn], r1[maxn], r2[maxn], tax[maxn], height[maxn];
//rk[i]代表第i位往后的排名，和sa相反，tax为桶
int*rk = r1, *tp = r2;
char s[maxn];
void rsort(int n, int m)
{
memset(tax, 0, (m + 1) * sizeof(tax[0]));
for (int i = 1; i <= n; i++)
tax[rk[i]]++;//当前排名装桶
for (int i = 1; i <= m; i++)
tax[i] += tax[i - 1];//计算桶的名词
for (int i = n; i >= 1; i--)
sa[tax[rk[tp[i]]]--] = tp[i];//分配名次
}
void get_sa(char*s)
{
int n = strlen(s + 1), m = 0;
for (int i = 1; i <= n; i++)
m = max(m, rk[i] = s[i]), tp[i] = i;
rsort(n, m);
for (int k = 1, p = 0; p < n; k <<= 1, m = p)
{
p = 0;
for (int i = n - k + 1; i <= n; i++)tp[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > k)
tp[++p] = sa[i] - k;
rsort(n, m);
swap(tp, rk);//复杂度为0(1)//仅用与单组数据
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++)
rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + k] == tp[sa[i - 1] + k]) ? p : ++p;
}
for (int i = 1, k = 0; i <= n; i++)
{
if (k)k--;
while (rk[i] > 1 && s[i + k] == s[sa[rk[i] - 1] + k])k++;
height[rk[i]] = k;
}
}
int col[maxn];
int ok;
int vis[maxn];
void del(int x)
{
if (col[x] == 0)return;
vis[col[x]]--;
if (vis[col[x]] == 0)
ok--;
}
void add(int x)
{
if (col[x] == 0)return;
vis[col[x]]++;
if (vis[col[x]] == 1)
ok++;
}
int L[10], R[10];
signed main()
{
int n;
n=2;
int pos = 0;
for (int i = 1; i <= n; i++)
{
L[i] = pos + 1;
scanf("%s", s + pos + 1);
pos += strlen(s + pos + 1);
R[i] = pos;
s[++pos] =i+'0';
}
get_sa(s);
for (int i = 1; i <= n; i++)
{
for (int j = L[i]; j <= R[i]; j++)
col[rk[j]] = i;//rk[j]代表以j为下表的字符串排名 所以col是带包所有排名的属于
}
deque<int>q;
int l = 1;
int ans = 0;
add(l);
for (int r = 2; r <= pos; ++r) {
while (!q.empty() && height[q.back()] >= height[r]) q.pop_back();
q.emplace_back(r);
add(r);
if (ok == n) {
while (ok == n && l < r) del(l), ++l;
--l, add(l);
}
while (!q.empty() && q.front() <= l) q.pop_front();//注意这里是等于，区间内第一个位置的height大小我们不关心
if (ok == n) ans = max(ans, height[q.front()]);
}//求解答案
cout << ans << endl;
}
活动打卡代码
AcWing 4757. 牛奶样品
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 1e6 + 10;
int sa[maxn], ht[maxn];
int s[maxn];
int n, k;
int rk[maxn];
int x[maxn], y[maxn], c[maxn];
// sa_i排名为i的下标（在字符串内）
void buildsa(int *s, int *sa, int *rk, int *ht, int n, int m = 200) // nlogn
{
s[n] = 0; //*用来处理溢出问题
for (register int i = 0; i < m; i++)
c[i] = 0;
for (register int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (register int i = 1; i < m; i++)
c[i] += c[i - 1];
for (register int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
for (int j = 0; j <= n; j++)
{
swap(x[j], y[j]);
}
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]); 取1-n-1
k = max(k - 1, 0ll);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
struct node
{
int l, r;
int maxx_id, minn_id;
} e[maxn];
bool check(int x)
{
int cnt = 0;
for (int i = 1; i < n; i++)
{
if (ht[i] >= x && (ht[i - 1] >= x))
{
e[cnt].r = i;
e[cnt].maxx_id = max(e[cnt].maxx_id, sa[i]);
e[cnt].minn_id = min(e[cnt].minn_id, sa[i]);
}
else if (ht[i] >= x && (i == 1 || ht[i - 1] < x))
{
e[++cnt].l = i, e[cnt].r = i;
e[cnt].maxx_id = max(sa[i], sa[i - 1]);
e[cnt].minn_id = min(sa[i], sa[i - 1]);
}
}
for (int i = 1; i <= cnt; i++)
{
if (e[i].r - e[i].l + 1 >= k - 1)
return 1;
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
buildsa(s, sa, rk, ht, n);
int l = 1, r = n;
int ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans;
}
活动打卡代码
AcWing 1403. 音乐主题
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 1e6 + 10;
int sa[maxn], ht[maxn];
int s[maxn];
int rk[maxn];
int x[maxn], y[maxn], c[maxn];
// sa_i排名为i的下标（在字符串内）
void buildsa(int *s, int *sa, int *rk, int *ht, int n, int m = 200) // nlogn
{
s[n] = 0; //*用来处理溢出问题
for (register int i = 0; i < m; i++)
c[i] = 0;
for (register int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (register int i = 1; i < m; i++)
c[i] += c[i - 1];
for (register int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
for (int j = 0; j <= n; j++)
{
swap(x[j], y[j]);
}
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]); 取1-n-1
k = max(k - 1, 0ll);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
struct node
{
int l, r;
int maxx_id, minn_id;
} e[maxn];
int n;
bool check(int x)
{
int cnt = 0;
for (int i = 1; i < 2 * n + 1; i++)
{
if (ht[i] >= x && (ht[i - 1] >= x))
{
e[cnt].r = i;
e[cnt].maxx_id = max(e[cnt].maxx_id, sa[i]);
e[cnt].minn_id = min(e[cnt].minn_id, sa[i]);
}
else if (ht[i] >= x && (i == 1 || ht[i - 1] < x))
{
e[++cnt].l = i, e[cnt].r = i;
e[cnt].maxx_id = max(sa[i], sa[i - 1]);
e[cnt].minn_id = min(sa[i], sa[i - 1]);
}
}
for (int i = 1; i <= cnt; i++)
{
int mx = e[i].maxx_id;
int mi = e[i].minn_id;
if (mx >= n + 1)
mx = e[i].maxx_id - n - 1;
if (mi >= n + 1)
mi = e[i].minn_id - n - 1;
if (mx == mi)
continue;
if (mx < mi)
swap(mx, mi);
if (mx >= mi + x)
return 1;
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
s[i - 1] = x;
}
int ans = 0;
s[n] = 180;
for (int i = 0; i <= 88; i++)
{
for (int j = n + 1; j <= 2 * n; j++)
{
s[j] = s[j - n - 1] + i;
}
buildsa(s, sa, rk, ht, 2 * n + 1);
int l = 5, r = n;
int anss = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
{
anss = mid;
l = mid + 1;
}
else
r = mid - 1;
}
ans = max(anss, ans);
}
cout << ans;
}
活动打卡代码
AcWing 4759. 新不同子串
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 1e6 + 10;
int sa[maxn], ht[maxn];
char s[maxn];
int rk[maxn];
int n;
void buildsa(char *s, int *sa, int *rk, int *ht, int n, int m = 128) // nlogn
{
static int x[maxn], y[maxn], c[maxn];
for (int i = 0; i < n; i++)
{
sa[i] = ht[i] = rk[i] = 0;
}
s[n] = 0; //*用来处理溢出问题
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
swap(x, y);
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]); 取1-n-1
k = max(k - 1, 0ll);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> s;
if (s[0] == '.')
break;
n = strlen(s);
buildsa(s, sa, rk, ht, n);
int tot = 0;
tot = n * (n + 1) / 2;
for (int i = 1; i < n; i++)
{
tot -= ht[i];
}
cout << tot << endl;
}
}
活动打卡代码
AcWing 4758. 不同子串
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int sa[maxn], ht[maxn];
char s[maxn];
int rk[maxn];
int n;
void buildsa(char *s, int *sa, int *rk, int *ht, int n, int m = 128) // nlogn
{
static int x[maxn], y[maxn], c[maxn];
for (int i = 0; i < n; i++)
{
sa[i] = ht[i] = rk[i] = 0;
}
s[n] = 0; //*用来处理溢出问题
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
swap(x, y);
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]); 取1-n-1
k = max(k - 1, 0ll);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> s;
if (s[0] == '.')
break;
n = strlen(s);
buildsa(s, sa, rk, ht, n);
int tot = 0;
tot = n * (n + 1) / 2;
for (int i = 1; i < n; i++)
{
tot -= ht[i];
}
cout << tot << endl;
}
}
活动打卡代码
AcWing 4680. 字符串乘方
nlogn 大常数 不过问题不大
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int sa[maxn], ht[maxn];
char s[maxn];
int rk[maxn];
int n;
void buildsa(char *s, int *sa, int *rk, int *ht, int n, int m = 128) // nlogn
{
static int x[maxn], y[maxn], c[maxn];
for (int i = 0; i < n; i++)
{
sa[i] = ht[i] = rk[i] = 0;
}
s[n] = 0; //*用来处理溢出问题
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[i] = s[i]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
// 利用基数排序离散化
for (int k = 1; k < n; k <<= 1)
{
int p = 0;
for (int i = n - 1; i >= n - k; i--)
y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k)
y[p++] = sa[i] - k;
// 先利用第二位关键字排序
for (int i = 0; i < m; i++)
c[i] = 0;
for (int i = 0; i < n; i++)
c[x[y[i]]]++;
for (int i = 1; i < m; i++)
c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
// 以上为基数排序
swap(x, y);
p = 1;
x[sa[0]] = 0;
y[n] = -1;
for (int i = 1; i < n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k])
{
x[sa[i]] = p - 1;
}
else
x[sa[i]] = p++;
if (p == n)
break;
m = p;
}
for (int i = 0; i < n; i++)
rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) // O(n)
{ // ht[i]=lcp(sa[i],sa[i-1]); 取1-n-1
k = max(k - 1, 0ll);
if (rk[i] == 0)
continue;
int j = sa[rk[i] - 1];
while (s[i + k] == s[j + k])
k++;
ht[rk[i]] = k; // 和前前面的lca
}
}
int Fmin[1001000][25]; // 查找最大值，Fmax[i][j]代表从i开始长度为（1<<j）的最大值
void st()
{
for (int i = 1; i < n; i++)
{
Fmin[i][0] = ht[i];
}
int k = log2(n - 1); // 最大的j,注：log！=log2
for (int j = 1; j <= k; j++)
for (int i = 1; i < n - (1 << j) + 1; i++)
{
Fmin[i][j] = min(Fmin[i][j - 1], Fmin[i + (1 << (j - 1))][j - 1]);
}
}
int RMQ(int l, int r)
{
int k = std::__lg(r - l + 1);
return min(Fmin[l][k], Fmin[r - (1 << k) + 1][k]);
}
int LCP(int u, int v)
{
if (u == v)
return n - u;
if (rk[u] > rk[v])
swap(u, v);
return RMQ(rk[u] + 1, rk[v]);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> s)
{
if (s[0] == '.')
break;
n = strlen(s);
buildsa(s, sa, rk, ht, n);
st();
bool ok = 1;
for (int i = 1; i <= n; i++) // a的长度
{
if (!ok)
break;
if (n % i == 1)
continue;
int begin = 1;
int okkk = 1;
for (int j = begin + i; j <= n; j += i)
{
int now = LCP(0, j - 1);
if (now < i)
{
okkk = 0;
}
}
if (okkk)
{
ok = 0;
cout << n / i << endl;
}
}
}
}
