Practice II 字符串

本来想做数论的……但是别的dalao都在做制胡窜

所以……

Chapter I KMP

KMP 最关键的不是这个半暴力的单模匹配

而是这个nxt数组 经常出一些奇怪的题 尤其是循环节可以直接由T-nxt[T]得到……神啊

总之记住nxt就是最长公共前后缀中前缀的尾指针

T1 poj3461 Oulipo

传送门

Time cost: 10min

纯纯的板子 真没啥可说的

就是每次清空nxt

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N = 1000005;
 5 #define rep(i,a,n) for(int i = a;i <= n;i++)
 6 #define ms(a,b) memset(a,b,sizeof a)
 7 
 8 char s[N],t[N];
 9 int S,T;
10 int nxt[N];
11 int ans;
12 void clr(){ms(nxt,0),ans = 0;}
13 void gnxt() {
14     int tmp = 0;
15     rep(i,2,T) {
16     while(tmp && t[tmp+1] != t[i]) tmp = nxt[tmp];
17     if(t[tmp+1] == t[i]) nxt[i] = ++tmp;
18     }
19 }
20 void KMP() {
21     int tmp = 0;
22     rep(i,1,S) {
23     while(tmp && t[tmp+1] != s[i]) tmp = nxt[tmp];
24     if(t[tmp+1] == s[i]) {
25         tmp++;
26         if(tmp == T) ans++;
27     }
28     }
29 }
30 
31 
32 int main() {
33     int q;
34     scanf("%d",&q);
35     while(q--) {
36     clr();
37     scanf("%s",t+1),scanf("%s",s+1);
38     S = strlen(s+1),T = strlen(t+1);
39     gnxt();
40     KMP();
41     printf("%d
",ans);
42     }
43 }
View Code

T2 poj 2406 Power strings

传送门

Time cost:55min

之前曾经遇到过……最后暴力滚粗

今天算是靠着打表理解了

由于nxt定义的时候刨去了串本身是自己的最长公共前后缀

在最后一次求nxt的时候 我们考虑被nxt[T]抛弃的部分(记为len)

如果这一段能整除T,那么考虑第二段len长的串

它与第一段len长的串是相等的

同理可以推到T/len倍

同时 nxt取最大值 故T-nxt[T]取最小

所以如果T是T-nxt[T]的整数倍 那么T-nxt[T]就是最小循环节

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N = 1000005;
 5 #define rep(i,a,n) for(int i = a;i <= n;i++)
 6 #define ms(a,b) memset(a,b,sizeof a)
 7 
 8 char s[N],t[N];
 9 int S,T;
10 int nxt[N];
11 int ans;
12 void clr(){ms(nxt,0),ans = 0;}
13 void gnxt() {
14     int tmp = 0;
15     rep(i,2,T) {
16     while(tmp && t[tmp+1] != t[i]) tmp = nxt[tmp];
17     if(t[tmp+1] == t[i]) nxt[i] = ++tmp;
18     }
19 }
20 void KMP() {
21     int tmp = 0;
22     rep(i,1,S) {
23     while(tmp && t[tmp+1] != s[i]) tmp = nxt[tmp];
24     if(t[tmp+1] == s[i]) {
25         tmp++;
26         if(tmp == T) ans++;
27     }
28     }
29 }
30 
31 
32 int main() {
33     while(1) {
34     clr();
35     scanf("%s",t+1);
36     T = strlen(t+1);
37     if(T == 1 && t[1] == '.') return 0;
38     gnxt();
39     if(T % (T - nxt[T]) == 0) printf("%d
",T/(T-nxt[T]));
40     else puts("1");
41     }
42 }
View Code

T3 CF526D Om Nom and Necklace

传送门

Time cost:45min

有了前一道题做铺垫 还是比较容易想到的

交叉没法做 我们视AB为循环节 

由于k给定 所以通过i和k可以求出一个循环节长度范围

如果这个长度是由nxt求出的最短循环节的整数倍就OK

实现的时候是 除len然后判断合法区间是否存在 这样就可以自动减掉后面剩的一段A

但是要注意 A或B为空的情况就是分成k段或者k+1段纯循环节(没有后缀) 可以特判

(实际A为空已经处理过了)

Code:

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000005;
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define ms(a,b) memset(a,b,sizeof a)

char s[N],t[N];
int S,T;
int nxt[N];
int ans;
void clr(){ms(nxt,0),ans = 0;}
void gnxt() {
    int tmp = 0;
    rep(i,2,T) {
    while(tmp && t[tmp+1] != t[i]) tmp = nxt[tmp];
    if(t[tmp+1] == t[i]) nxt[i] = ++tmp;
    }
}
void KMP() {
    int tmp = 0;
    rep(i,1,S) {
    while(tmp && t[tmp+1] != s[i]) tmp = nxt[tmp];
    if(t[tmp+1] == s[i]) {
        tmp++;
        if(tmp == T) ans++;
    }
    }
}
int n,k;

int main() {
    scanf("%d%d",&n,&k);
    scanf("%s",t+1);
    T = n;
    gnxt();
    rep(i,1,T) {
    int len = i - nxt[i];
    if(i % (k+1) == 0 && (i / (k+1)) % len == 0) putchar('1');//lenb==0
    else {
        //circular subsequence range
        int upp = i / k,down = i / (k + 1) + 1;
        upp = upp / len;
        down = (down + len - 1) / len;
        if(upp >= down) putchar('1');
        else putchar('0');
    }
    }
    puts("");
    return 0;
}
View Code

Chapter II Trie

字典树 比较重要的地方就是空间

一定要考虑好空间问题不要超限

其他的话还是比较好理解的 当做一棵26叉树

T1 poj3630 Phone list

Time cost: 25min

经典的Trie树板子题

先把所有串压进去然后再每一个串查

Code:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #define rep(i,a,n) for(int i = a;i <= n;i++)
 7 #define per(i,n,a) for(int i = n;i >= a;i--)
 8 #define inf 2147483647
 9 using namespace std;
10 typedef long long ll;
11 inline int read() {
12     int as = 0,fu = 1;
13     char c = getchar();
14     while(c < '0' || c > '9') {
15         if(c == '-') fu = -1;
16         c = getchar();
17     }
18     while(c >= '0' && c <= '9') {
19         as = as * 10 + c - '0';
20         c = getchar();
21     }
22     return as * fu;
23 }
24 const int N = 10005;
25 const int M = 12;
26 #define ms(a) memset(a,0,sizeof(a));
27 //head
28 char s[N][M];
29 struct trie {
30     int nxt[N * M][12],val[N * M];
31     int cnt;
32     inline void clear() {
33         ms(nxt);
34         ms(val);
35         cnt = 0;
36     }
37     inline void build(char p[]) {
38         int now = 0;
39         rep(i,0,strlen(p) - 1) {
40             if(!nxt[now][p[i] - '0'])
41                 nxt[now][p[i] - '0'] = ++cnt;
42             now = nxt[now][p[i] - '0'];
43         }
44         val[now] = 1;
45     }
46     inline bool query(char p[]) {
47         int now = 0;
48         rep(i,0,strlen(p) - 1) {
49             if(val[now]) return 0;
50             now = nxt[now][p[i] - '0'];
51         }
52         return 1;
53     }
54 } T;
55 
56 int main() {
57     int q = read();
58     while(q--) {
59         bool flag = 1;
60         ms(s);
61         T.clear();
62         int n = read();
63         rep(i,1,n) {
64             scanf("%s",s[i]);
65             T.build(s[i]);
66         }
67         rep(i,1,n) {
68             flag = T.query(s[i]);
69             if(flag == 0) break;
70         }
71         flag ? printf("YES
") : printf("NO
") ;
72     }
73     return 0;
74 }
View Code

T2 poj2945 Find the clones

Time cost:25min

题目要求输出被复制x次的有多少种

依然先把所有串建好树

那么就在query的时候开一个res表示val[now]的有多少个

注意每次找到的时候要把val清空

Code:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #define rep(i,a,n) for(int i = a;i <= n;i++)
 7 #define per(i,n,a) for(int i = n;i >= a;i--)
 8 #define inf 2147483647
 9 using namespace std;
10 typedef long long ll;
11 inline int read() {
12     int as = 0,fu = 1;
13     char c = getchar();
14     while(c < '0' || c > '9') {
15         if(c == '-') fu = -1;
16         c = getchar();
17     }
18     while(c >= '0' && c <= '9') {
19         as = as * 10 + c - '0';
20         c = getchar();
21     }
22     return as * fu;
23 }
24 const int N = 20005;
25 const int M = 25;
26 #define ms(a) memset(a,0,sizeof(a));
27 //head
28 char s[N][M];
29 struct trie {
30     int nxt[N * M][5],val[N * M];
31     int res[N];
32     int cnt;
33     inline void clear() {
34         ms(nxt);
35         ms(val);
36         ms(res);
37         cnt = 0;
38     }
39     inline int cng(char c) {
40         if(c == 'A') return 0;
41         if(c == 'G') return 1;
42         if(c == 'T') return 2;
43         if(c == 'C') return 3;
44         else return 4;
45     }
46     inline void build(char p[]) {
47         int now = 0;
48         rep(i,0,strlen(p) - 1) {
49             int c = cng(p[i]);
50             if(!nxt[now][c])
51                 nxt[now][c] = ++cnt;
52             now = nxt[now][c];
53         }
54         val[now]++;
55     }
56     inline void query(char p[]) {
57         int now = 0;
58         rep(i,0,strlen(p) - 1) {
59             int c = cng(p[i]);
60             now = nxt[now][c];
61         }
62         res[val[now]]++;
63         val[now] = 0;
64     }
65 } T;
66 
67 int main() {
68     while(1) {
69         int n = read();
70         int m = read();
71         if(!n && !m) break;
72         T.clear();
73         ms(s);
74         rep(i,1,n) {
75             scanf("%s",s[i]);
76             T.build(s[i]);
77         }
78         rep(i,1,n) T.query(s[i]);
79         rep(i,1,n) {
80             printf("%d
",T.res[i]);
81         }
82     }
83     return 0;
84 }
View Code

T3 poj1816 Wild words

Time cost:65min

好像这题有个名字叫模糊查询……

?的话就额外开一个节点 查的时候单独查

*的话就暴搜除掉的位数……

注意S* 也能匹配S

所以搜*的时候要在搜结束节点之前

然后就是空间……这道题nxt数组开1e5*30*30都不行 每个节点存答案的时候必须用vector

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 typedef long long ll;
 7 #define ms(a,b) memset(a,b,sizeof a)
 8 #define rep(i,a,n) for(int i = a;i <= n;i++)
 9 #define per(i,n,a) for(int i = n;i >= a;i--)
10 const int N = 100001;
11 const int M = 28;
12 //HEAD
13 int m,n;
14 vector<int> mem[N*M];
15 int ans[N],top;
16 int nxt[N][M],cnt;
17 void clr() {
18     cnt = 0;
19     ms(nxt,0);
20 }
21 int cng(char op) {
22     if(op == '*') return 26;
23     if(op == '?') return 27;
24     return op - 'a';
25 }
26 
27 char p[35];
28 int len;
29 void ins(int idx) {
30     int cur = 0;
31     rep(i,0,len - 1) {
32     if(!nxt[cur][cng(p[i])])
33         nxt[cur][cng(p[i])] = ++cnt;
34     cur = nxt[cur][cng(p[i])];
35     }
36     mem[cur].push_back(idx);
37 }
38 
39 void query(int cur,int pos) {
40     if(nxt[cur][26]) 
41     rep(i,pos,len) query(nxt[cur][26],i);
42     
43     if(pos == len) {
44     int sze = mem[cur].size();
45     rep(i,0,sze - 1)
46         ans[++top] = mem[cur][i];
47     return;
48     }
49     if(nxt[cur][cng(p[pos])])
50     query(nxt[cur][cng(p[pos])],pos+1);
51     if(nxt[cur][27])
52     query(nxt[cur][27],pos+1);
53 }
54 
55 int main() {
56     scanf("%d%d",&n,&m);
57     clr();
58     rep(i,1,n) {
59     scanf("%s",p);
60     len = strlen(p);
61     ins(i-1);
62     }
63     while(m--) {
64     scanf("%s",p);
65     top = 0;
66     len = strlen(p);
67     query(0,0);
68     if(!top) {
69         puts("Not match");
70         continue;
71     }
72     sort(ans+1,ans+1+top);
73     top = unique(ans+1,ans+1+top) - ans - 1;
74     rep(i,1,top) printf("%d ",ans[i]);
75     puts("");
76     }
77     return 0;
78 }
View Code

T4 CF633C Spy Syndrome 2

传送门

Time cost:105min

发现做字符串时间格外长……还是不熟练

一开始想着先反过来再匹配……

事实证明考虑前一位是否匹配的时候如果是正的还是要遍历一遍

所以直接就倒着做就行

O(n^2)可以做出类似链式前向星的东西 然后从最后一位输出就可以了

注意标记初值要设成-1 

然后递归输出的时候注意顺序不要反了就行

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #include<vector>
 7 #define ms(a,b) memset(a,b,sizeof a)
 8 #define rep(i,a,n) for(int i = a;i <= n;i++)
 9 #define per(i,n,a) for(int i = n;i >= a;i--)
10 #define inf 2147483647
11 using namespace std;
12 typedef long long ll;
13 ll read() {
14     ll as = 0,fu = 1;
15     char c = getchar();
16     while(c < '0' || c > '9') {
17         if(c == '-') fu = -1;
18         c = getchar();
19     }
20     while(c >= '0' && c <= '9') {
21         as = as * 10 + c - '0';
22         c = getchar();
23     }
24     return as * fu;
25 }
26 const int N = 100005;
27 //head
28 int n,m;
29 char S[10005];
30 char p[N][1005];
31 int cng(char op){return op >= 'a' ? op - 'a' : op - 'A';}
32 
33 int nxt[1000005][26],val[1000005],tot;
34 void ins(char *s,int id) {
35     int cur = 0;
36     int len = strlen(s);
37     rep(i,0,len-1) {
38         int c = cng(s[i]);
39         if(!nxt[cur][c]) nxt[cur][c] = ++tot;
40         cur = nxt[cur][c];
41     }
42     val[cur] = id;
43 }
44 
45 int pre[N],ans[N];
46 void query(int x) {
47     int cur = 0;
48     per(i,x,0) {
49         int c = cng(S[i]);
50         cur = nxt[cur][c];
51         if(!cur) return;
52         if(val[cur]) {
53             if(ans[i-1] || !i) {
54                 pre[x] = i-1;
55                 ans[x] = val[cur];
56                 return;
57             }
58         }
59     }
60 }
61 
62 void output(int x) {
63     if(~pre[x]) output(pre[x]);
64     printf("%s ",p[ans[x]]);
65 }
66 
67 int main() {
68     n = read();
69     scanf("%s",S);
70     m = read();
71     rep(i,1,m) {
72         scanf("%s",p[i]);
73         ins(p[i],i);
74     }
75     ms(pre,-1);
76     rep(i,0,n-1) query(i);
77     output(n-1),puts("");
78     return 0;
79 }
View Code

Chapter III AC自动机

我太菜了……板子调了好久……

总体来讲 AC自动机与KMP相同的是 fail很重要

不同的是 这个匹配也很重要

都可以拿来出题

总体来讲 沿着fail的路线也可以搞事情(poj4052),沿着trie树向上走也可以做标记

总之 只有节点维护标记 节点之间的联系只有trie边和fail 考虑清楚就行了

T1 poj 4052 Hrinity

Time cost:95min

这么水一个题我做这么长时间……太菜了

题意大概是给出一堆模式串(还有缩写)在文本串里找

其中被包含的子串不计数

不能在文本串里去掉因为可能剩下的还能匹配小串

所以就第一次先把所有匹配了的串都打上标记 然后再扫一遍把被普通节点覆盖的终止节点去掉

注意:

1.不要把自己去了

2.转换的时候用strcpy比较方便 但别用反了……

3.去掉小串之前要先把访问数组清空

Code:

  1 Source Code
  2 
  3 Problem: 4052        User: dvb
  4 Memory: 36408K        Time: 594MS
  5 Language: G++        Result: Accepted
  6 Source Code
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<algorithm>
 10 #include<cmath>
 11 #include<queue>
 12 #include<vector>
 13 #define itn int
 14 #define inf 2147483647
 15 #define eps 1e-9
 16 #define ms(a,b) memset(a,b,sizeof a)
 17 #define rep(i,a,n) for(int i = a;i <= n;i++)
 18 #define per(i,n,a) for(int i = n;i >= a;i--)
 19 using namespace std;
 20 typedef long long ll;
 21 ll read() {
 22     ll as = 0,fu = 1;
 23     char c = getchar();
 24     while(c < '0' || c > '9') {
 25         if(c == '-') fu = -1;
 26         c = getchar();
 27     }
 28     while(c >= '0' && c <= '9') {
 29         as = as * 10 + c - '0';
 30         c = getchar();
 31     }
 32     return as * fu;
 33 }
 34 //head
 35 int n;
 36 char p[2505][1105],S[5100005];
 37 char P[5100005];
 38 
 39 void cng(char s[]) {
 40     int len = strlen(s);
 41     int cur = 0;
 42     rep(i,0,len-1) {
 43     if(s[i] == '[') {i++;
 44         int num = 0;
 45         char op;
 46         while(s[i] != ']') {
 47         if(s[i] >= '0' && s[i] <= '9') num = num * 10 + s[i] - '0';
 48         else op = s[i];
 49         i++;
 50         }
 51         rep(i,1,num) P[cur++] = op;
 52     }
 53     else P[cur++] = s[i];
 54     }
 55     P[cur] = '';
 56     strcpy(s,P);
 57 }
 58 
 59 
 60 struct node {
 61     int val,fail;
 62     int nxt[26];
 63     void init() {
 64     ms(nxt,0),val = fail = 0;
 65     }
 66 }t[2750005];
 67 int tot = 1;
 68 
 69 void ins(char *s,int id) {
 70     int len = strlen(s);
 71     int cur = 1;
 72     rep(i,0,len-1) {
 73     int c = s[i] - 'A';
 74     if(!t[cur].nxt[c])
 75         t[cur].nxt[c] = ++tot,t[tot].init();
 76     cur = t[cur].nxt[c];
 77     }
 78     t[cur].val = id;
 79 }
 80 
 81 
 82 void getfail() {
 83     rep(i,0,25) t[0].nxt[i] = 1;
 84     queue<int> q;
 85     q.push(1);
 86     while(!q.empty()) {
 87     int u = q.front(),v,w;
 88     q.pop();
 89     rep(i,0,25) {
 90         v = t[u].fail;
 91         while(!t[v].nxt[i]) v = t[v].fail;
 92         v = t[v].nxt[i];
 93         w = t[u].nxt[i];
 94         if(w) t[w].fail = v,q.push(w);
 95         else t[u].nxt[i] = v;
 96     }
 97     }
 98 }
 99 
100 
101 bool vis[2750005];
102 bool flag[2505];
103 void query() {
104     int len = strlen(S);
105     int cur = 1;
106     rep(i,0,len-1) {
107     cur = t[cur].nxt[S[i]-'A'];
108     if(t[cur].val) {
109         flag[t[cur].val] = 1;
110         continue;
111     }
112     int tmp = cur;
113     while(tmp && !vis[tmp]) {
114         vis[tmp] = 1;
115         flag[t[tmp].val] = 1;
116         tmp = t[tmp].fail;
117     }
118     }
119 }
120 
121 void del(char *s,int id) {
122     int len = strlen(s);
123     int cur = 1;
124     rep(i,0,len-1) {
125     cur = t[cur].nxt[s[i]-'A'];
126     int tmp = cur;
127     while(tmp && !vis[tmp]) {
128         if(t[tmp].val && t[tmp].val ^ id) {
129         vis[tmp] = 1;
130         flag[t[tmp].val] = 0;
131         }
132         tmp = t[tmp].fail;
133     }
134     }
135 }
136 
137 void clr() {
138     rep(i,1,tot) t[i].init();
139     tot = 1;
140     ms(flag,0);
141 }
142 
143 int main() {
144     int T = read();
145     while(T--) {
146     clr();
147     
148     n = read();
149     rep(i,1,n) {
150         scanf("%s",p[i]);
151         cng(p[i]);
152         ins(p[i],i);
153     }
154     
155     getfail();
156     
157     scanf("%s",S);
158     cng(S);
159     ms(vis,0),query();
160     
161     ms(vis,0);
162     rep(i,1,n) 
163         if(flag[i]) del(p[i],i);
164     
165     int ans = 0;
166     rep(i,1,n) ans += flag[i];
167     printf("%d
",ans);
168     
169     }
170     return 0;
171 }
View Code

Chapter IV manacher

回文串...看起来比较不常见 但是出了就得会 

听说后面有个回文自动机? 看到了再说吧...

T1  poj3974 Palindrome 

Time cost: 35min

基础的回文串题 调了一下之前的板子 换了种写法

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #define ms(a,b) memset(a,b,sizeof a)
 7 #define rep(i,a,n) for(int i = a;i <= n;i++)
 8 #define per(i,n,a) for(int i = n;i >= a;i--)
 9 #define inf 2147483647
10 using namespace std;
11 typedef long long ll;
12 ll read() {
13     ll as = 0,fu = 1;
14     char c = getchar();
15     while(c < '0' || c > '9') {
16         if(c == '-') fu = -1;
17         c = getchar();
18     }
19     while(c >= '0' && c <= '9') {
20         as = as * 10 + c - '0';
21         c = getchar();
22     }
23     return as * fu;
24 }
25 const int N = 1000005;
26 //head
27 char s[N<<1],t[N];
28 int R[N<<1];
29 int n,m,T,maxx;
30 void manacher() {
31     int id = 0,pos = 0,r = 0;
32     rep(i,1,n) {
33     if(pos > i) r = min(R[id * 2 - i],pos - i);
34     else r = 1;
35     while(s[i - r] == s[i + r]) r++;
36     if(r + i > pos) {
37         pos = r + i;
38         id = i;
39     }
40     R[i] = r;
41     }
42 }
43 
44 void clr() {
45     ms(R,0);
46     maxx = 0;
47 }
48 int main() {
49     while(scanf("%s",t+1),t[1] != 'E') {
50     clr();
51     m = strlen(t+1);
52     s[n = 0] = 0;
53     rep(i,1,m) {
54         s[++n] = '#';
55         s[++n] = t[i];
56     }
57     s[++n] = '#';
58     s[n+1] = 1;
59     manacher();
60     rep(i,1,n) maxx = max(maxx,R[i]);
61     printf("Case %d: %d
",++T,maxx - 1);
62     }
63     return 0;
64 }  
View Code

T2 luogu P1659 [国家集训队]拉拉队排练 

传送门

Time cost:45min

发现自己还是不太明白原理....

这道题做法就是找出所有长为奇数的回文串

发现长的回文串一定包含较短的

所以求一遍最长长度的后缀和就是真正的个数

数据范围较大 使用快速幂

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #define ms(a,b) memset(a,b,sizeof a)
 7 #define rep(i,a,n) for(int i = a;i <= n;i++)
 8 #define per(i,n,a) for(int i = n;i >= a;i--)
 9 #define inf 2147483647
10 using namespace std;
11 typedef long long ll;
12 ll read() {
13     ll as = 0,fu = 1;
14     char c = getchar();
15     while(c < '0' || c > '9') {
16         if(c == '-') fu = -1;
17         c = getchar();
18     }
19     while(c >= '0' && c <= '9') {
20         as = as * 10 + c - '0';
21         c = getchar();
22     }
23     return as * fu;
24 }
25 const int N = 1000005;
26 const ll mod = 19930726ll;
27 //head
28 char s[N];
29 int r[N];
30 ll n,k,ans = 1;
31 ll num[N];
32 void manacher() {
33     int id = 0,pos = 0,x = 0;
34     rep(i,1,n) {
35     if(pos > i) x = min(r[(id<<1)-i] , pos - i);
36     else x = 1;
37     while(s[i+x] == s[i-x]) x++;
38     if(x + i > pos) pos = x + i,id = i;
39     r[i] = x;
40     num[r[i]-1<<1|1]++;
41     }
42 }
43 ll ksm(ll a,ll b) {
44     ll tmp = 1;
45     while(b) {
46     if(b & 1) tmp = tmp * a % mod;
47     a = a * a % mod;
48     b >>= 1;
49     }
50     return tmp;
51 }
52 
53 
54 int main() {
55     n = read(),k = read();
56     scanf("%s",s+1);
57     s[0] = '&';
58     manacher();
59     per(i,n+1>>1,1) {
60     ll l = i-1<<1|1;
61     num[l] += num[l+2];
62     if(k >= num[l]) {
63         ans = (ans * ksm(l,(ll)num[l])) % mod;
64         k -= num[l];
65     } else {
66         ans = (ans * ksm(l,k)) % mod;
67         printf("%lld
",ans);
68         k = 0;
69         break;
70     }
71     }
72     if(k) puts("-1");
73     return 0;
74 }  
View Code

T3 luogu  P4555 [国家集训队]最长双回文串

传送门

Time cost:85min

难度明显上来了

不能直接暴力 考虑枚举中间的连接点

然后思路就是找以当前点为左右端点的最远另一端点(记为L,R)

注意真正的回文串长度是所求回文半径长度-1

所以就在manacher里面找到最长回文串的时候求出其左右端点的答案

注意这个答案还可以被L(R)更新

所以我们找到所有的下标为‘#’(插入的特殊字符)的位置互相更新(具体见代码main)

复杂度O(n)

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #define ms(a,b) memset(a,b,sizeof a)
 7 #define rep(i,a,n) for(int i = a;i <= n;i++)
 8 #define per(i,n,a) for(int i = n;i >= a;i--)
 9 #define inf 2147483647
10 using namespace std;
11 typedef long long ll;
12 ll read() {
13     ll as = 0,fu = 1;
14     char c = getchar();
15     while(c < '0' || c > '9') {
16         if(c == '-') fu = -1;
17         c = getchar();
18     }
19     while(c >= '0' && c <= '9') {
20         as = as * 10 + c - '0';
21         c = getchar();
22     }
23     return as * fu;
24 }
25 const int N = 200005;
26 //head
27 int n,maxx;
28 char s[N],t[N];
29 int r[N],L[N],R[N];
30 void manacher() {
31     int pos = 0,maxr = 0,x = 0;
32     rep(i,1,n) {
33     if(maxr > i) x = min(r[(pos<<1)-i],maxr-i);
34     else x = 1;
35     while(s[i + x] == s[i - x]) x++;
36     if(i + x > maxr) maxr = i+x,pos = i;
37     r[i] = x;
38     L[i+r[i]-1] = max(L[i+r[i]-1],r[i]-1);
39     R[i-r[i]+1] = max(R[i-r[i]+1],r[i]-1);
40     }
41 }
42 
43 int main() {
44     scanf("%s",t+1);
45     s[++n] = 0;
46     int l = strlen(t+1);
47     rep(i,1,l) {
48     s[++n] = '#';
49     s[++n] = t[i];
50     }
51     s[++n] = '#';
52     s[++n] = '%';
53     manacher();
54     rep(i,1,n>>1) R[i<<1] = max(R[i<<1],R[i-1<<1]-2);
55     per(i,n>>1,1) L[i<<1] = max(L[i<<1],L[i+1<<1]-2);
56     rep(i,1,n>>1) if(R[i<<1] && L[i<<1]) maxx = max(maxx,L[i<<1] + R[i<<1]);
57     printf("%d
",maxx);
58     return 0;
59 }
View Code

To be continued...

https://www.luogu.org/problemnew/show/P1659

> 别忘了 总有人在等着你
原文地址:https://www.cnblogs.com/yuyanjiaB/p/9765150.html