manacher
1 //返回s的最长回文子串的长度 2 int Manacher(char* s){ 3 int len=strlen(s); 4 for(int i=len;i>=0;i--){ 5 s[2*i+2]=s[i]; 6 s[2*i+1]='#'; 7 } 8 s[0]='*'; 9 int id=0,m=0; 10 for(int i=2;i<len*2+1;i++){ 11 if(r[id]+id>i) r[i]=min(r[2*id-i],r[id]+id-i); 12 else r[i]=1; 13 while(s[i-r[i]]==s[i+r[i]]) r[i]++; 14 if(id+r[id]<i+r[i]) id=i; 15 if(m<r[i]) m=r[i]; 16 } 17 return m-1; 18 }
Tire树
1 const int maxnode=50000*200+10; 2 const int sigma=2; 3 #define CLR(m,a) memset(m,a,sizeof(m)) 4 struct Trie{ 5 int ch[maxnode][sigma]; 6 int val[maxnode]; 7 int sz; 8 //添加需要的挂载信息 9 10 void init(){ 11 CLR(ch[0],0); 12 sz=1; 13 } 14 int idx(char c){return c-'0';} 15 //插入字符串s，附加信息为v（v必须非零） 16 void inser(char *s,int v){ 17 int u=0,n=strlen(s); 18 for(int i=0;i<n;i++){ 19 int c=idx(s[i]); 20 if(!ch[u][c]){ 21 CLR(ch[sz],0); 22 ch[u][c]=sz++; 23 } 24 u=ch[u][c]; 25 } 26 val[u]=v; 27 } 28 void find(char* s){ 29 int u=0,n=strlen(s); 30 for(int i=0;i<n;i++){ 31 int c=idx(s[i]); 32 if(!ch[u][c]) return -1; 33 u=ch[u][c]; 34 } 35 return val[u]; 36 } 37 };
节点较多时用下面这个
1 const int maxnode=2000010; 2 const int sigma=26; 3 //Trie树 4 struct Trie{ 5 int head[maxnode],nex[maxnode]; 6 char ch[maxnode]; 7 int val[maxnode]; 8 int sz; 9 10 void init(){ 11 head[0]=-1; 12 sz=1; 13 } 14 //插入 15 void insert_(char* s,int v){ 16 int u=0,v,n=strlen(s); 17 for(int i=0;i<n;i++){ 18 int ok=0; 19 for(v=head[u];~v;v=nex[v]) if(ch[v]==s[i]){ 20 ok=1; 21 break; 22 } 23 if(!ok){ 24 v=sz++; 25 ch[v]=s[i]; 26 val[v]=0; 27 nex[v]=head[u]; 28 head[u]=v; 29 head[v]=-1; 30 } 31 u=v; 32 } 33 val[u]=v; 34 } 35 //查询 36 void query(char* s){ 37 int u=0,v,n=strlen(s); 38 for(int i=0;i<n;i++){ 39 int ok=0; 40 for(v=head[u];~v;v=nex[v]) if(ch[v]==s[i]){ 41 ok=1; 42 u=v; 43 break; 44 } 45 if(!ok) return ; 46 } 47 return val[u]; 48 } 49 };
01字典树
1 const int maxnode = 100010 * 32; 2 const int sigma = 2; 3 struct Tre{ 4 int ch[maxnode][sigma]; 5 LL val[maxnode]; 6 int sz; 7 void init(){ 8 sz = 1; 9 val[0] = 0; 10 memset(ch[0], 0, sizeof(ch[0])); 11 } 12 void add(LL x){ 13 int u = 0, n = 32; 14 for(int i = n; i >= 0; i--){ 15 int c = (x >> i) & 1; 16 if(!ch[u][c]){ 17 memset(ch[sz], 0, sizeof(ch[sz])); 18 val[sz] = 0; 19 ch[u][c] = sz++; 20 } 21 u = ch[u][c]; 22 } 23 val[u] = x; 24 } 25 //返回与x异或最大的值val[u]; 26 LL query(LL x){ 27 int u = 0, n = 32; 28 for(int i = n; i >= 0; i--){ 29 int c = (x >> i) & 1; 30 if(ch[u][c ^ 1]) u = ch[u][c ^ 1]; 31 else u = ch[u][c]; 32 } 33 return val[u]; 34 } 35 }tre;
KMP
1 const int maxn=1000010; 2 int pl,sl; //要先计算长度！！！ 3 int nex[maxn]; 4 char s[maxn],p[maxn]; 5 int ans=0;// 6 7 void getnex(char *p) 8 { 9 int j=0,k=-1; 10 nex[0]=-1; 11 while(j<pl){ 12 if(k==-1||p[j]==p[k]) nex[++j]=++k; 13 else k=nex[k]; 14 } 15 } 16 //拿p去匹配s 17 void KMP(char *s,char *p) 18 { 19 getnex(p); 20 int i=0,j=0; 21 while(i<sl){ 22 if(j==-1||s[i]==p[j]) {i++;j++;} 23 else j=nex[j]; 24 if(j==pl) return i-pl+1; //看问题需要！！！ 25 } 26 }
1 //p是模板串 2 const int maxn=1010; 3 char s[maxn],p[maxn]; 4 int f[maxn]; 5 int lens,lenp; 6 void getfail(char* p){ 7 f[0]=f[1]=0; 8 for(int i=1;i<lenp;i++){ 9 int j=f[i]; 10 while(j&&p[j]!=p[i]) j=f[j]; 11 f[i+1]=p[i]==p[j]?j+1:0; 12 } 13 return ; 14 } 15 int KMP(char* s,char* p){ 16 lens=srelen(s); 17 lenp=strlen(p); 18 getfail(p); 19 int j=0; 20 for(int i=0;i<lens;i++){ 21 while(j&&s[i]!=p[j]) j=f[j]; 22 if(s[i]==p[j]) j++; 23 if(j==lenp) return i-m+1; //找到p 24 } 25 return -1; //没找到p 26 }
扩展KMP
1 const int maxn = 100010; 2 char s[maxn], t[maxn]; 3 int ex[maxn], nxt[maxn]; 4 int lens, lent; 5 6 void getnxt(){ 7 nxt[0] = lent; 8 int a = 0, p = 0; 9 for(int i = 1; i < lent; i++){ 10 if(i >= p || i + nxt[i - a] >= p){ 11 if(i >= p) p = i; 12 while(p < lent && t[p] == t[p - i]) p++; 13 nxt[i] = p - i; 14 a = i; 15 }else nxt[i] = nxt[i - a]; 16 } 17 } 18 void exkmp(char *s, char *t, int *ex){ 19 getnxt(t); 20 int a = 0, p = 0; 21 for(int i = 0; i < lens; i++){ 22 if(i >= p || i + nxt[i - a] >= p){ 23 if(i >= p) p = i; 24 while(p < lens && p - i < lent && s[p] == t[p - i]) p++; 25 ex[i] = p - i; 26 a = i; 27 }else ex[i] = nxt[i - a]; 28 } 29 }
ac自动机
1 const int maxnode=11000; 2 const int sigma=26; 3 const int maxn=160; // 4 5 struct AC 6 { 7 int ch[maxnode][sigma]; 8 int f[maxnode],val[maxnode],last[maxnode]; 9 int sz; 10 int cnt[maxn]; // 11 12 void init() 13 { 14 CLR(ch[0],0); 15 CLR(cnt,0); 16 sz=1; 17 } 18 int idx(char c) {return c-'a';} 19 20 void inser(char *s,int v) 21 { 22 int u=0,n=strlen(s); 23 for(int i=0;i<n;i++){ 24 int c=idx(s[i]); 25 if(!ch[u][c]){ 26 CLR(ch[sz],0); 27 val[sz]=0; 28 ch[u][c]=sz++; 29 } 30 u=ch[u][c]; 31 } 32 val[u]=v; 33 } 34 void print(int u) 35 { 36 if(u){ 37 cnt[val[u]]++; 38 print(last[u]); 39 } 40 } 41 void fin(char *s) 42 { 43 int n=strlen(s); 44 int u=0; 45 for(int i=0;i<n;i++){ 46 int c=idx(s[i]); 47 while(u&&!ch[u][c]) u=f[u]; 48 u=ch[u][c]; 49 if(val[u]) print(u); 50 else if(last[u]) print(last[u]); 51 } 52 } 53 void getfail() 54 { 55 queue<int> q; 56 f[0]=0; 57 for(int c=0;c<sigma;c++){ 58 int u=ch[0][c]; 59 if(u){ 60 f[u]=0; 61 q.push(u); 62 last[u]=0; 63 } 64 } 65 while(!q.empty()){ 66 int r=q.front(); 67 q.pop(); 68 for(int c=0;c<sigma;c++){ 69 int u=ch[r][c]; 70 if(!u) continue; 71 q.push(u); 72 int v=f[r]; 73 while(v&&!ch[v][c]) v=f[v]; 74 f[u]=ch[v][c]; 75 last[u]=val[f[u]]?f[u]:last[f[u]]; 76 } 77 } 78 } 79 };
后缀数组
1 int s[maxn]; 2 int sa[maxn], t1[maxn],t2[maxn],c[maxn]; 3 int h[maxn],rank[maxn]; 4 int n; 5 void build_sa(int n, int m){ 6 int i, *x = t1, *y = t2; 7 for(i = 0; i < m; i++) c[i] = 0; 8 for(i = 0; i < n; i++) c[x[i] = s[i]]++; 9 for(i = 1; i < m; i++) c[i] += c[i-1]; 10 for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; 11 12 for(int k = 1; k <= n; k <<= 1){ 13 int p = 0; 14 for(i = n-k; i < n; i++) y[p++] = i; 15 for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i]-k; 16 for(i = 0; i < m; i++) c[i] = 0; 17 for(i = 0; i < n; i++) c[x[y[i]]]++; 18 for(i = 1; i< m; i++) c[i] += c[i-1]; 19 for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; 20 swap(x,y); 21 p = 1; 22 x[sa[0]] = 0; 23 for(i = 1; i < n; i++) 24 x[sa[i]] = y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]? p-1 : p++; 25 if(p>=n) break; 26 m=p; 27 } 28 } 29 30 void geth(int n){ 31 int i, j, k=0; 32 for(i = 0; i <= n; i++) rank[sa[i]]=i; 33 for(i = 0; i < n; i++) { 34 if(k) k--; 35 j = sa[rank[i]-1]; 36 while(s[i+k]==s[j+k]) k++; 37 h[rank[i]] = k; 38 } 39 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1001; 4 5 //sa[i] ：排名第 i 的后缀在哪（i 从 1 开始） 6 //rk[i]：后缀 i 排第几 （i 从 0 开始） 7 //h[i]：排名为 i 和 i-1 的两个后缀的最长公共前缀(LCP)长度 （i 从 2 开始） 8 int s[maxn]; 9 int sa[maxn], t1[maxn],t2[maxn],c[maxn]; 10 int h[maxn],rk[maxn]; 11 void build_sa(int n, int m){ 12 int i, *x = t1, *y = t2; 13 for(i = 0; i < m; i++) c[i] = 0; 14 for(i = 0; i < n; i++) c[x[i] = s[i]]++; 15 for(i = 1; i < m; i++) c[i] += c[i-1]; 16 for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; 17 18 for(int k = 1; k <= n; k <<= 1){ 19 int p = 0; 20 for(i = n-k; i < n; i++) y[p++] = i; 21 for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i]-k; 22 for(i = 0; i < m; i++) c[i] = 0; 23 for(i = 0; i < n; i++) c[x[y[i]]]++; 24 for(i = 1; i< m; i++) c[i] += c[i-1]; 25 for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; 26 swap(x,y); 27 p = 1; 28 x[sa[0]] = 0; 29 for(i = 1; i < n; i++) 30 x[sa[i]] = y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]? p-1 : p++; 31 if(p>=n) break; 32 m=p; 33 } 34 } 35 36 void geth(int n){ 37 int i, j, k=0; 38 for(i = 1; i <= n; i++) rk[sa[i]]=i; 39 for(i = 0; i < n; i++) { 40 if(k) k--; 41 j = sa[rk[i]-1]; 42 while(s[i+k]==s[j+k]) k++; 43 h[rk[i]] = k; 44 } 45 } 46 47 int dp[maxn][20]; 48 void rmq_init(int n){ 49 int k = 0; 50 while(1<<(k+1) <= n) k++; 51 for(int i = 1; i <= n; i++) dp[i][0] = h[i]; 52 for(int i = 1; i <= k; i++){ 53 for(int j = 1; j + (1<<i) - 1 <= n; j++){ 54 dp[i][j] = min(dp[i][j-1], dp[i+(1<<j-1)][j-1]); 55 } 56 } 57 } 58 int rmq(int a, int b){ 59 if(a > b) swap(a, b); // 60 a++; 61 int k = 0; 62 while(1<<(k+1) <= b-a+1) k++; 63 return min(dp[a][k], dp[b - (1<<k) + 1][k]); 64 } 65 char str[maxn]; 66 int main(){ 67 scanf("%s", str); 68 int n = strlen(str); 69 for(int i = 0; i < n; i++) s[i] = str[i] - 'a' + 1; 70 build_sa(n+1, 300); 71 geth(n); 72 // for(int i = 1; i <= n; i++) cout<<sa[i]<<" "; 73 // cout<<endl; 74 // for(int i = 0; i < n; i++) cout<<rk[i]<<" "; 75 // cout<<endl; 76 // for(int i = 2; i <= n; i++) cout<<h[i]<<" "; 77 // cout<<endl; 78 // int a, b; 79 rmq_init(n); 80 while(scanf("%d %d", &a, &b)) 81 cout<<rmq(rk[a], rk[b])<<endl; 82 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1001; 4 /* 5 * 后缀数组 6 * DC3算法,复杂度O(n) 7 * 所有的相关数组都要开三倍 8 */ 9 const int MAXN = 2010; 10 #define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb)) 11 #define G(x) ((x) < tb ? (x) * 3 + 1 : ((x)-tb) * 3 + 2) 12 13 int wa[MAXN * 3], wb[MAXN * 3], wv[MAXN * 3], wss[MAXN * 3]; 14 15 int c0(int *r, int a, int b) 16 { 17 return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2]; 18 } 19 20 int c12(int k, int *r, int a, int b) 21 { 22 if(k == 2) 23 { 24 return r[a] < r[b] || (r[a] == r[b] && c12(1, r, a + 1, b + 1)); 25 } 26 else 27 { 28 return r[a] < r[b] || (r[a] == r[b] && wv[a + 1] < wv[b + 1]); 29 } 30 } 31 32 void sort(int *r, int *a, int *b, int n, int m) 33 { 34 int i; 35 for (i = 0; i < n; i++) 36 { 37 wv[i] = r[a[i]]; 38 } 39 for (i = 0; i < m; i++) 40 { 41 wss[i] = 0; 42 } 43 for (i = 0; i < n; i++) 44 { 45 wss[wv[i]]++; 46 } 47 for (i = 1; i < m; i++) 48 { 49 wss[i] += wss[i - 1]; 50 } 51 for (i = n - 1; i >= 0; i--) 52 { 53 b[--wss[wv[i]]] = a[i]; 54 } 55 } 56 57 void dc3(int *r, int *sa, int n, int m) 58 { 59 int i, j, *rn = r + n; 60 int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p; 61 r[n] = r[n+1] = 0; 62 for (i = 0; i < n; i++) 63 { 64 if (i % 3 != 0) 65 { 66 wa[tbc++] = i; 67 } 68 } 69 sort(r + 2, wa, wb, tbc, m); 70 sort(r + 1, wb, wa, tbc, m); 71 sort(r, wa, wb, tbc, m); 72 for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++) 73 { 74 rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++; 75 } 76 if (p < tbc) 77 { 78 dc3(rn, san, tbc, p); 79 } 80 else 81 { 82 for (i = 0; i < tbc; i++) 83 { 84 san[rn[i]] = i; 85 } 86 } 87 for (i = 0; i < tbc; i++) 88 { 89 if (san[i] < tb) 90 { 91 wb[ta++] = san[i] * 3; 92 } 93 } 94 if (n % 3 == 1) 95 { 96 wb[ta++] = n - 1; 97 } 98 sort(r, wb, wa, ta, m); 99 for (i = 0; i < tbc; i++) 100 { 101 wv[wb[i] = G(san[i])] = i; 102 } 103 for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++) 104 { 105 sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++]; 106 } 107 for (; i < ta; p++) 108 { 109 sa[p] = wa[i++]; 110 } 111 for (; j < tbc; p++) 112 { 113 sa[p] = wb[j++]; 114 } 115 } 116 117 // str和sa也要三倍 118 void da(int str[], int sa[], int rank[], int height[], int n,int m) 119 { 120 for (int i = n; i < n * 3; i++) 121 { 122 str[i] = 0; 123 } 124 dc3(str, sa, n+1, m); 125 int i, j, k = 0; 126 for (i = 0; i <= n; i++) 127 { 128 rank[sa[i]] = i; 129 } 130 for (i = 0; i < n; i++) 131 { 132 if(k) 133 { 134 k--; 135 } 136 j = sa[rank[i] - 1]; 137 while (str[i + k] == str[j + k]) 138 { 139 k++; 140 } 141 height[rank[i]] = k; 142 } 143 } 144 //sa[i] ：排名第 i 的后缀在哪（i 从 1 开始） 145 //rk[i]：后缀 i 排第几 （i 从 0 开始） 146 //h[i]：排名为 i 和 i-1 的两个后缀的最长公共前缀(LCP)长度 （i 从 2 开始） 147 int s[maxn]; 148 int sa[maxn], t1[maxn],t2[maxn],c[maxn]; 149 int h[maxn],rk[maxn]; 150 int dp[maxn][20]; 151 void rmq_init(int n){ 152 int k = 0; 153 while(1<<(k+1) <= n) k++; 154 for(int i = 1; i <= n; i++) dp[i][0] = h[i]; 155 for(int i = 1; i <= k; i++){ 156 for(int j = 1; j + (1<<i) - 1 <= n; j++){ 157 dp[i][j] = min(dp[i][j-1], dp[i+(1<<j-1)][j-1]); 158 } 159 } 160 } 161 int rmq(int a, int b){ 162 if(a > b) swap(a, b); // 163 a++; 164 int k = 0; 165 while(1<<(k+1) <= b-a+1) k++; 166 return min(dp[a][k], dp[b - (1<<k) + 1][k]); 167 } 168 char str[maxn]; 169 int main(){ 170 scanf("%s", str); 171 int n = strlen(str); 172 for(int i = 0; i < n; i++) s[i] = str[i] - 'a' + 1; 173 da(s, sa, rk, h, n, 300); 174 // for(int i = 3; i <= n; i++) cout<<sa[i]<<" "; 175 // cout<<endl; 176 // for(int i = 0; i < n; i++) cout<<rk[i]<<" "; 177 // cout<<endl; 178 // for(int i = 2; i <= n; i++) cout<<h[i]<<" "; 179 // cout<<endl; 180 int a, b; 181 rmq_init(n); 182 while(scanf("%d %d", &a, &b)) 183 cout<<rmq(rk[a], rk[b])<<endl; 184 }