记录编号	140323	评测结果	AAAAAAAAAAAAAAAAAAAAAA
题目名称	[ONTAK 2010] 回文等价	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.441 s
提交时间	2014-11-21 17:08:00	内存使用	41.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<set>
using namespace std;
typedef long long LL;
LL MOD=1000000000+7;
const int SIZEN=1000010,INF=0x7fffffff/2;
char S[2*SIZEN];//加#后的字符串
int n,N;//N是加#后的字符串长度
char str[SIZEN];//原字符串
int R[2*SIZEN];//回文半径
int id[2*SIZEN]={0};//等价类的编号(用该类中第一个元素编号)
set<int> dif[SIZEN];//每个位置和哪些等价类不同
/*为了卡内存,这里采用了一种奇怪的技巧:和i不同的那些等价类存放在dif[i/2]中,
因为但反正不存在有意义的和,和某个'#'不同的等价类*/
void print(set<int> &a){//调试接口,打印一个set
	set<int>::iterator key;
	for(key=a.begin();key!=a.end();key++) cout<<(*key)<<" ";cout<<endl;
}
void merge(set<int> &a,set<int> &b,int k=INF){//将a中不超过k的元素都压入b
	set<int>::iterator key;
	for(key=a.begin();key!=a.end();key++){
		if(*key>=k) return;
		b.insert(*key);
	}
}
void work(void){
	for(int i=0;i<N;i++){//将每个等价类的不等关系合并
		if(id[i]&&id[i]!=i)//注意,只考虑指向较小等价类的不等关系
			merge(dif[i/2],dif[id[i]/2],id[i]);
	}
	LL ans=1;
	for(int i=1;i<N;i++){
		if(id[i]==i){//除了那些确定不等的等价类外,26个元素任意选
			ans*=26-dif[i/2].size();
			ans%=MOD;
		}
	}
	printf("%d\n",ans);
}
void marknew(int x){//试图将x作为一个新的等价类的起点,保证x不可能是零
	if('a'<=S[x]&&S[x]<='z'&&!id[x]) id[x]=x;
}
void Manacher(void){
	R[0]=1;
	int mx=1,p=0;
	for(int i=1;i<N;i++){//大部分是普通的Manacher算法
		//mx是"第一个未被编号的"位置(自动无视那些#)
		if(i==mx) marknew(mx);//i在先前的过程中未被确定和任一等价类相等,故它成为一个独立等价类
		//这是新等价类的唯一生成方式
		if(mx>i) R[i]=min(R[2*p-i],mx-i);
		else R[i]=1;
		while(S[i-R[i]]==S[i+R[i]]){
			id[i+R[i]]=id[i-R[i]];//对于相等的元素,试图标记其等价类(i-R[i]所在等价类一定已知)
			R[i]++;
		}
		if(i+R[i]>=mx&&id[i-R[i]]) dif[(i+R[i])/2].insert(id[i-R[i]]);
		if(i+R[i]>mx){
			p=i;
			mx=i+R[i];
		}
	}
}
void read(void){
	scanf("%s",str);
	n=strlen(str);
	int tot=0;
	S[tot++]='@',S[tot++]='#';//S[0]='@',防止越界问题
	for(int i=0;i<n;i++) S[tot++]=str[i],S[tot++]='#';
	N=tot;
}
int main(){
	freopen("palindromic.in","r",stdin);
	freopen("palindromic.out","w",stdout);
	read();
	Manacher();
	work();
	return 0;
}