回文树练习 Part1

时间：2023-03-09 16:20:35
回文树练习 Part1

　　URAL - 1960   Palindromes and Super Abilities

　　回文树水题，每次插入时统计数量即可。

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 struct Pam_Tree{

     int nxt[maxn][];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p;

     int newnode(int l) {

         For(i,,) nxt[p][i]=;

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     void add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[cur][c]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[get_fail(fail[cur])][c];

             nxt[cur][c]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[cur][c];

         cnt[lst]++;

     }

     void count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i];

     }

 };

 Pam_Tree pt;

 void Debug(int *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(ll *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(double *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(char *s){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     cout<<s+<<endl;

  }

 int dcmp(double x) {

     if(fabs(x)<=eps) return ;

     return x<?-:;

 }

 struct Point{

     ll x,y;

     Point(ll x=,ll y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y); }

     bool operator < (const Point &a)const { if(a.x==x) return y>a.y; return x<a.x; }

 };

 ll Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }

 ll Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }

 double len(Vector a) { return sqrt(Dot(a,a)); }

 struct node{

     ll x,id;

     node(ll x=,ll id=):x(x),id(id) {}

     bool operator < (const node &a)const { if(x==a.x) return id<a.id; return x>a.x; }

 };

 char s[maxn];

 void solve() {

     pt.init();

     scanf("%s",s+);

     int l=strlen(s+);

     For(i,,l) pt.add(s[i]-'a'),printf("%d ",pt.p-);

     puts("");

 }

 int main() {

     int tt=;

     while(tt--) solve();

     return ;

 }

　　HDU - 5658  CA Loves Palindromic

　　回文树水题，因为长度只有1000，n*n预处理出所有答案即可

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 struct Pam_Tree{

     int nxt[maxn][];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p;

     int newnode(int l) {

         For(i,,) nxt[p][i]=;

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     void add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[cur][c]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[get_fail(fail[cur])][c];

             nxt[cur][c]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[cur][c];

         cnt[lst]++;

     }

     void count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i];

     }

 };

 Pam_Tree pt;

 void Debug(int *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(ll *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(double *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(char *s){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     cout<<s+<<endl;

  }

 int dcmp(double x) {

     if(fabs(x)<=eps) return ;

     return x<?-:;

 }

 struct Point{

     ll x,y;

     Point(ll x=,ll y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y); }

     bool operator < (const Point &a)const { if(a.x==x) return y>a.y; return x<a.x; }

 };

 ll Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }

 ll Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }

 double len(Vector a) { return sqrt(Dot(a,a)); }

 struct node{

     ll x,id;

     node(ll x=,ll id=):x(x),id(id) {}

     bool operator < (const node &a)const { if(x==a.x) return id<a.id; return x>a.x; }

 };

 char s[maxn];

 int ans[][];

 void solve() {

     pt.init();

     scanf("%s",s+);

     int l=strlen(s+),r,q;

     For(i,,l) {

         pt.init();

         For(j,i,l) {

             pt.add(s[j]-'a');

             ans[i][j]=pt.p-;

         }

     }

     scanf("%d",&q);

     while(q--) {

         scanf("%d%d",&l,&r);

         printf("%d\n",ans[l][r]);

     }

 }

 int main() {

     int tt=;

     cin>>tt;

     while(tt--) solve();

     return ;

 }

　　HYSBZ - 3676 回文串

　　回文树水题

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 struct Pam_Tree{

     int nxt[maxn][];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p;

     int newnode(int l) {

         For(i,,) nxt[p][i]=;

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     void add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[cur][c]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[get_fail(fail[cur])][c];

             nxt[cur][c]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[cur][c];

         cnt[lst]++;

     }

     void count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i];

     }

     ll ans() {

         ll ans=;

         Fore(i,p-,) {

             ans=max(1LL*cnt[i]*len[i],ans);

         }

         return ans;

     }

 };

 Pam_Tree pt;

 void Debug(int *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(ll *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(double *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(char *s){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     cout<<s+<<endl;

  }

 int dcmp(double x) {

     if(fabs(x)<=eps) return ;

     return x<?-:;

 }

 struct Point{

     ll x,y;

     Point(ll x=,ll y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y); }

     bool operator < (const Point &a)const { if(a.x==x) return y>a.y; return x<a.x; }

 };

 ll Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }

 ll Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }

 double len(Vector a) { return sqrt(Dot(a,a)); }

 struct node{

     ll x,id;

     node(ll x=,ll id=):x(x),id(id) {}

     bool operator < (const node &a)const { if(x==a.x) return id<a.id; return x>a.x; }

 };

 char s[maxn];

 ll ans;

 void solve() {

     pt.init();

     scanf("%s",s+);

     int l=strlen(s+),r,q;

     For(i,,l) pt.add(s[i]-'a');

     pt.count();

     printf("%lld\n",pt.ans());

 }

 int main() {

     int tt=;

     while(tt--) solve();

     return ;

 }

　　HYSBZ - 2565 最长双回文串

　　回文树瞎搞即可，正着插入统计一遍个数，倒着插入统计一遍个数即可

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 const int MAXN=;

 struct Pam_Tree{

     int nxt[maxn][];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p;

     int newnode(int l) {

         For(i,,) nxt[p][i]=;

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     int add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[cur][c]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[get_fail(fail[cur])][c];

             nxt[cur][c]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[cur][c];

         cnt[lst]++;

         return len[lst];

     }

     void count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i];

     }

 };

 Pam_Tree pt;

 void Debug(int *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(ll *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(double *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(char *s){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     cout<<s+<<endl;

  }

 int dcmp(double x) {

     if(fabs(x)<=eps) return ;

     return x<?-:;

 }

 struct Point{

     ll x,y;

     Point(ll x=,ll y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y); }

     bool operator < (const Point &a)const { if(a.x==x) return y>a.y; return x<a.x; }

 };

 ll Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }

 ll Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }

 double len(Vector a) { return sqrt(Dot(a,a)); }

 struct node{

     ll x,id;

     node(ll x=,ll id=):x(x),id(id) {}

     bool operator < (const node &a)const { if(x==a.x) return id<a.id; return x>a.x; }

 };

 int ans,ansl[MAXN],ansr[MAXN];

 char s[MAXN];

 void solve() {

     pt.init();

     scanf("%s",s+);

     int l=strlen(s+);

     For(i,,l) ansl[i]=pt.add(s[i]-'a');

     pt.init();

     Fore(i,l,) ansr[i]=pt.add(s[i]-'a');

     For(i,,l-) ans=max(ansl[i]+ansr[i+],ans);

     cout<<ans<<endl;

 }

 int main() {

     int tt=;

     while(tt--) solve();

     return ;

 }

　　HYSBZ - 2160 拉拉队排练

　　回文树插入后统计长度回文子串的长度和数量，排序后直接求前k个乘积即可

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 const int MAXN=;

 struct Pam_Tree{

     int nxt[maxn][];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p;

     int newnode(int l) {

         For(i,,) nxt[p][i]=;

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     int add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[cur][c]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[get_fail(fail[cur])][c];

             nxt[cur][c]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[cur][c];

         cnt[lst]++;

         return len[lst];

     }

     void count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i];

     }

 };

 Pam_Tree pt;

 void Debug(int *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(ll *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(double *a,int l){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     For(i,,l) cout<<a[i]<<" ";

     cout<<endl;

 }

 void Debug(char *s){

     cout<<"Debug-----!!!-_-!!----------"<<endl;

     cout<<s+<<endl;

  }

 int dcmp(double x) {

     if(fabs(x)<=eps) return ;

     return x<?-:;

 }

 struct Point{

     ll x,y;

     Point(ll x=,ll y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y); }

     bool operator < (const Point &a)const { if(a.x==x) return y>a.y; return x<a.x; }

 };

 ll Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }

 ll Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }

 double len(Vector a) { return sqrt(Dot(a,a)); }

 struct node{

     ll x,id;

     node(ll x=,ll id=):x(x),id(id) {}

     bool operator < (const node &a)const { if(x==a.x) return id<a.id; return x>a.x; }

 };

 struct Node{

     int l;

     ll x;

     bool operator < (const Node &a)const {

         if(l==a.l) return x<a.x;

         return l>a.l;

     }

 };

 ll quick_pow(ll a,ll b) {

     ll base=;

     while(b) {

         if(b&) base=base*a%Mod;

         a=a*a%Mod;b>>=;

     }

     return base%Mod;

 }

 char s[maxn];

 int l,rt;

 ll k;

 Node ans[maxn];

 void solve() {

     pt.init();rt=;

     cin>>l>>k;

     scanf("%s",s+);

     For(i,,l) pt.add(s[i]-'a');

     pt.count();

     For(i,,pt.p-){

             if(pt.len[i]% ) ans[rt].l=pt.len[i],ans[rt++].x=pt.cnt[i];

     }

     sort(ans+,ans+rt);

     ll cur=;

 //    For(i,1,rt-1) cout<<ans[i].l<<" "<<ans[i].x<<endl;

     For(i,,rt-) {

         if(k==) break;

         if(k<=ans[i].x) cur=(quick_pow(ans[i].l,k)%Mod*cur)%Mod,k=;

         else cur=(quick_pow(ans[i].l,ans[i].x)*cur%Mod)%Mod,k-=ans[i].x;

     }

     if(k) cout<<-<<endl;

     else cout<<cur%Mod<<endl;

 }

 int main() {

     int tt=;

     while(tt--) solve();

     return ;

 }

　　HDU 5157 Harry and magic string

　　求不向交的回文子串的对数

　　直接将整个串正向插入，求每次插入时以该位置为右端点的回文子串有多少个，

　　再将整个串反向插入到回文树中，同样统计子串的个数，最后统计求和即可

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 const int MAXN=;

 struct Pam_Tree{

     vector<pii >nxt[maxn];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p,x;

     int newnode(int l) {

         nxt[p].clear();

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int find(int cur,int c){

         For(i,,nxt[cur].sz) {

             if(nxt[cur][i-].fir==c) return nxt[cur][i-].sec;

         }

         return ;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     int add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         x=find(cur,c);

         if(!x) {

             int now=newnode(len[cur]+);

             fail[now]=find(get_fail(fail[cur]),c);

             nxt[cur].pb(mkp(c,now));

             num[now]=num[fail[now]]+;

             x=now;

         }

         lst=x;

         cnt[lst]++;

         return num[lst];

     }

     ll count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i],cnt[fail[i]]%=Mod;

     }

 };

 Pam_Tree pt;

 ll ans[maxn],ans2;

 ll cnt1,cnt2,cnt;

 char s[maxn];

 int n;

 void solve() {

     while(~scanf("%s",s+)){

         pt.init();met(ans,);

         int l=strlen(s+);cnt1=;cnt2=;

         For(i,,l) ans[i]=ans[i-]+pt.add(s[i]-'a');

         cnt2=pt.count();

         pt.init();

         Fore(i,l,) ans2=pt.add(s[i]-'a'),cnt1=cnt1+ans2*ans[i-];

         cout<<cnt1<<endl;

     }

 }

 int main() {

     int tt=;

     while(tt--) solve();

     return ;

 }

　　CodeForces 17E

　　题目大意：求相交的回文子串有多少对

　　直接考虑相交不好考虑，可以反着来，用回文子串的对数减去不相交的回文子串的数量即可，回文树搞搞就行。

　　题目内存要求较高，可以考虑用map或vector来存next数组

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 const int MAXN=;

 struct Pam_Tree{

     unordered_map<int,int>nxt[];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p;

     int newnode(int l) {

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         For(i,,) nxt[i].clear();

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     int add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[c][cur]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[c][get_fail(fail[cur])];

             nxt[c][cur]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[c][cur];

         cnt[lst]++;

         return num[lst];

     }

     ll count() {

         ll res=;

         Fore(i,p-,) cnt[fail[i]]+=cnt[i],cnt[fail[i]]%=Mod;

         Fore(i,p-,) res+=cnt[i],res%=Mod;

         return res;

     }

 };

 Pam_Tree pt;

 ll ans[maxn],ans2;

 ll cnt1,cnt2,cnt;

 char s[maxn];

 int n;

 void solve() {

     cin>>n;

     pt.init();

     cin>>s+;met(ans,);

     int l=strlen(s+);cnt1=;cnt2=;

     For(i,,l) ans[i]=ans[i-]+pt.add(s[i]-'a'),ans[i]%=Mod;

     cnt2=pt.count();

     pt.init();

     Fore(i,l,) ans2=pt.add(s[i]-'a'),cnt1=(cnt1+ans2*ans[i-]%Mod)%Mod;

     cout<<((cnt2*1LL*(cnt2-)/)%Mod-cnt1+Mod)%Mod<<endl;

 }

 int main() {

     int tt=;

     while(tt--) solve();

     return ;

 }

　　HDU 4426 Palindromic Substring

　　将整个串插入回文树中，对于每个人，统计其所有回文子串的价值，排序，最后取第k个

　　因为k可能会超int，子串的数量也会超int，所以全用long long了

　　 
 #include<bits/stdc++.h>

 using namespace std;

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define endl '\n'

 typedef pair<int,int> pii;

 const long long linf=1LL<<;

 const int iinf=;

 const double dinf=1e15;

 const int Mod=;

 typedef long long ll;

 typedef long double ld;

 const int maxn=;

 const int MAXN=;

 struct Pam_Tree{

     int nxt[maxn][];

     int fail[maxn];

     int cnt[maxn];

     int num[maxn];

     int len[maxn];

     int S[maxn];

     int lst,n,p,x;

     int newnode(int l) {

         For(i,,) nxt[p][i]=;

         cnt[p]=;

         num[p]=;

         len[p]=l;

         return p++;

     }

     void init() {

         p=;

         newnode();newnode(-);

         lst=;n=;S[n]=-;

         fail[]=;

     }

     int get_fail(int x) {

         while(S[n-len[x]-]!=S[n]) x=fail[x];

         return x;

     }

     int add(int c) {

         S[++n]=c;

         int cur=get_fail(lst);

         if(!nxt[cur][c]) {

             int now=newnode(len[cur]+);

             fail[now]=nxt[get_fail(fail[cur])][c];

             nxt[cur][c]=now;

             num[now]=num[fail[now]]+;

         }

         lst=nxt[cur][c];

         cnt[lst]++;

         return num[lst];

     }

     ll count() {

         Fore(i,p-,) cnt[fail[i]]+=cnt[i],cnt[fail[i]]%=Mod;

     }

 };

 Pam_Tree pt;

 int v[][];

 ll k[],cnt;

 ll f[],u,vv;

 map<ll,ll>mp;

 void dfs(int now,int x,ll st) {

     if(now!= && now!=) mp[st]+=pt.cnt[now];

     For(i,,) {

         if(pt.nxt[now][i]){

             dfs(pt.nxt[now][i],x,(st+v[x][i]*1LL*f[(pt.len[now]+)/]%Mod)%Mod);

         }

     }

 }

 map<ll,ll>::iterator it;

 int n,m;

 char s[];

 void solve() {

     pt.init();

     scanf("%d%d",&n,&m);

     scanf("%s",s+);

     For(i,,n) pt.add(s[i]-'a');

     pt.count();

     For(i,,m) {

         scanf("%lld",&k[i]);

         For(j,,)

             scanf("%d",&v[i][j]);

     }

     For(i,,m) {

         mp.clear();

         dfs(,i,);dfs(,i,);cnt=k[i];

         for(it=mp.begin();it!=mp.end();it++) {

             u=(*it).first;vv=(*it).sec;

 //            cout<<u<<" "<<vv<<endl;

             if(cnt-vv>)cnt-=vv;

             else {

                 cnt=;

                 printf("%lld\n",u%Mod);

                 break;

             }

         }

     }

 }

 int main() {

     f[]=;

     For(i,,) f[i]=f[i-]*26LL%Mod;

     int tt=;

     cin>>tt;

     while(tt--) solve(),cout<<endl;

     return ;

 }

相关文章