S+6-字符串
A. 文本校对
- 暴力HASH就好了
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
95const int N = 1e6 + 5, base = 19260817, mod = 998244353;
int n, m, h[N], pw[N], inv[N], now[N];
string s;
ll qpow(int x, int y)
{
ll res = 0;
while (y)
{
if (y & 1)
res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
void insert(int pos, int x)
{
string ss = " ";
for (int i = 1; i < pos; i++)
ss += s[i];
ss += x;
for (int i = pos; i <= n; i++)
ss += s[i];
for (int i = 1; i <= n; i++) {
if (now[i] >= pos)
now[i]++;
}
n++;
s = ss;
for (int i = 1; i <= n; i++)
{
h[i] = (h[i - 1] * base % mod + s[i] - 'a') % mod;
}
}
int query(int l, int r)
{
return (h[r] - h[l - 1] * pw[r - l + 1] % mod + mod) % mod;
}
int check(int x, int i, int j)
{
return query(i, i + x - 1) == query(j, j + x - 1);
}
signed main()
{
IOS;
cin >> s >> m;
s = ' ' + s;
n = s.size() - 1;
pw[0] = 1;
for (int i = 1; i < N; i++)
{
pw[i] = pw[i - 1] * base % mod;
}
for (int i = 1; i <= n; i++)
{
now[i] = i;
h[i] = (h[i - 1] * base % mod + s[i] - 'a') % mod;
}
while (m--)
{
char op, x;
cin >> op;
if (op == 'I')
{
char x;
int p;
cin >> x >> p;
p = min(p, n - 1);
insert(p, x);
}
else
{
int i, j;
cin >> i >> j;
int l = 1, r = min(n - now[i] + 1, n - now[j] + 1), res = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid, now[i], now[j]))
{
l = mid + 1;
res = mid;
}
else
{
r = mid - 1;
}
}
cout << res << endl;
}
}
return 0;
}
B. 最长回文
- 可以马拉车直接做
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
45char chs[22000005];
int p[22000005], cnt, ans;
void manacher()
{
int mx = 0, mid = 0;
for (int i = 0; i <= cnt; i++)
{
if (i < mx)
{
p[i] = min(mx - i, p[mid * 2 - i]);
}
else
{
p[i] = 1;
}
while (i + p[i] <= cnt && i - p[i] >= 0 && chs[i + p[i]] == chs[i - p[i]])
{
p[i]++;
}
if (i + p[i] > mx)
{
mx = i + p[i];
mid = i;
}
ans = max(p[i], ans);
}
}
int main()
{
int n;
cin >> n;
getchar();
getchar();
char ch = getchar();
chs[0] = '#';
while (ch >= 'a' && ch <= 'z')
{
chs[++cnt] = ch;
chs[++cnt] = '#';
ch = getchar();
}
manacher();
printf("%d\n", ans - 1);
return 0;
} - 二分+HASH
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
58typedef unsigned long long ull;
typedef long long ll;
constexpr int N = 1145141, base = 127;
int n, ans;
ull h[N], hRev[N], p[N];
char s[N], sRev[N];
ull getHashAll(char s[], int len) {
ull ret = 0;
for (int i = 1; i <= len; i++)
ret = base * ret + (ull)s[i];
return ret;
}
void getHashSeq(char s[], int len, ull h[]) {
h[0] = 0;
for (int i = 1; i <= len; i++)
h[i] = h[i - 1] * base + s[i];
}
void getP(int len) {
p[0] = 1;
for (int i = 1; i <= len; i++)
p[i] = p[i - 1] * base;
}
ull getSubHash(ull h[], int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
scanf("%d\n%s", &n, s + 1);
for (int i = 1; i <= n; i++)
sRev[n - i + 1] = s[i];
getHashSeq(s, n, h);
getHashSeq(sRev, n, hRev);
getP(n + 1);
for (int i = 1; i <= n; i++) {
int l = 0, r = min(i - 1, n - i), mid;
while (l <= r) {
mid = (l + r) >> 1;
if (getSubHash(h, i - mid, i - 1) == getSubHash(hRev, (n - i + 1) - mid, n - i)) {
ans = max(ans, (mid << 1) | 1);
l = mid + 1;
} else
r = mid - 1;
}
}
for (int i = 1; i < n; i++) {
int l = 1, r = min(i, n - i), mid;
while (l <= r) {
mid = (l + r) >> 1;
if (getSubHash(h, i - mid + 1, i) == getSubHash(hRev, n - i + 1 - mid, n - i)) {
ans = max(ans, mid << 1);
l = mid + 1;
} else
r = mid - 1;
}
}
printf("%d", ans);
return 0;
}
C. 二维匹配
- 二维HASH
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/*
二维hash板子
先对整体取哈希，把每个大小为 A×B 的存入 unordered_map；然后对每个子矩阵取哈希，判断是否在 map 中即可。时间复杂度 O(n^2)。
g_{x, y}=(a_{x, y}+g_{x−1, y} × p2 + g_{x, y−1} × p1 − g{x−1, y−1} × p1 × p2) mod p
H(x1,y1,x2,y2)=(H(1,1,x2,y2)−H(1,1,x1−1,y2)×p2x2−x1+1−H(1,1,x2,y1−1)×p1y2−y1+1+H(1,1,x1−1,y1−1)×p2x2−x1+1×p1y2−y1+1)modM
*/
using namespace std;
const int base1 = 131, base2 = 13331;
long long n, m, q, a, b, mt[5010][5010], s[5010][5010], l1[5010], l2[5010];
map<long long, bool> HASH;
void handle(long long ll, long long rr) {
for (int i = 1; i <= ll; i++) {
for (int j = 1; j <= rr; j++) {
char s;
cin >> s;
mt[i][j] = s - '0' + 1;
}
}
for (int i = 1; i <= rr; i++) {
l1[i] = l1[i - 1] * base1;
l2[i] = l2[i - 1] * base2;
}
for (int i = 1; i <= ll; i++) {
for (int j = 1; j <= rr; j++) {
s[i][j] = s[i][j - 1] * base1 + mt[i][j];
}
}
for (int i = 1; i <= ll; i++) {
for (int j = 1; j <= rr; j++) {
s[i][j] += s[i - 1][j] * base2;
}
}
}
int main() {
l1[0] = l2[0] = 1;
cin >> n >> m >> a >> b;
handle(n, m);
for (int i = a; i <= n; i++) {
for (int j = b; j <= m; j++) {
HASH[s[i][j] - s[i - a][j]*l2[a] - s[i][j - b]*l1[b] + s[i - a][j - b]*l2[a]*l1[b]] = 1;
}
}
cin >> q;
for (int k = 1; k <= q; k++) {
handle(a, b);
if (HASH[s[a][b]])cout << 1 << endl;
else cout << 0 << endl;
}
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
62int n, m, trie[410][26], fail[410], now, dep[410], state[410];
bool late[410];
queue<int> q;
void insert(string s) {
int len = s.length(), p = 0;
for (int i = 0; i < len; i++) {
if (!trie[p][s[i] - 'a'])
trie[p][s[i] - 'a'] = ++now;
dep[trie[p][s[i] - 'a']] = dep[p] + 1;
p = trie[p][s[i] - 'a'];
}
late[p] = true;
}
void init() {
for (int i = 0; i < 26; i++)
if (trie[0][i])
q.push(trie[0][i]);
while (!q.empty()) {
int x = q.front();
q.pop();
int Fail = fail[x];
state[x] = state[Fail];
if (late[x])
state[x] |= (1 << dep[x]);
for (int i = 0; i < 26; i++) {
if (trie[x][i])
fail[trie[x][i]] = trie[Fail][i], q.push(trie[x][i]);
else
trie[x][i] = trie[Fail][i];
}
}
}
int query(string t) {
int len = t.length(), p = 0, ans = 0;
unsigned predigit = 1;
for (int i = 0; i < len; i++) {
int tp = t[i] - 'a';
p = trie[p][tp];
predigit <<= 1;
if (predigit & state[p])
predigit |= 1, ans = max(ans, i + 1);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
insert(s);
}
init();
for (int i = 1; i <= m; i++) {
string t;
cin >> t;
cout << query(t) << "\n";
}
return 0;
}
F. 两段异或和
- 01trie去找最大异或就好了
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
43const int N=4e5+10;
int n,tr[N*32][2],a[N],s[N],l[N],r[N],tot,ans;
void insert(int x){
int u=0;
for(int i=30;i>=0;i--){
int c=(x>>i)&1;
if(!tr[u][c]) tr[u][c]=++tot;
u=tr[u][c];
}
}
int query(int x){
int u=0,res=0;
for(int i=30;i>=0;i--){
int c=(x>>i)&1;
if(tr[u][c^1]){
res+=(1<<i);
u=tr[u][c^1];
}
else u=tr[u][c];
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]^a[i];
insert(0);
for(int i=1;i<=n;i++){
l[i]=max(l[i-1],query(s[i]));
insert(s[i]);
}
memset(tr,0,sizeof tr);
tot=0;
for(int i=n;i>=1;i--) s[i]=s[i+1]^a[i];
insert(0);
for(int i=n;i>=1;i--){
r[i]=max(r[i+1],query(s[i]));
insert(s[i]);
}
for(int i=1;i<n;i++) ans=max(ans,l[i]+r[i+1]);
cout<<ans<<'\n';
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ysmmm的快乐小屋！
