【ACM-ICPC 2018 南京赛区网络预赛 I. Skr】 manacher+hash_综合

I.skr
题意：求一个字符串所有本质不同的回文子串的贡献和，每个符合条件的子串的贡献就是该子串代表的数字值。
该问题可以转化为两个子问题来考虑，第一个子问题就是找出所有本质不同的回文子串，第二个问题就是计算该子串对答案的贡献。
我们首先来考虑第一个问题，我们首先要解决的是如何找出所有的回文子串，如果以某个点为中心去搜就太慢了，我们发现manacher算法寻找最长回文子串的过程中其实已经找了每个可能出现过的回文子串，我们怎么o(1)的判断是否该子串已经出现过呢，当然就是判重神器hash表，（听大佬说pdbs的hash_table也能过，没用过这个库，暂且咕咕），我们首先将整个串hash一下，然后对每个找到的回文子串的hash值丢到hash表中，如果当前hash值没有出现过，我们就要计算这个子串的贡献，我们怎么计算贡献呢，就先把整个串逆置过来hash一下，
比如
$12324hash一下就变成了42321$
$我们如果想得到232所对应的值，$
$那么就是1232-1000也就是232，$
$这样就很方便O(1)的计算这个贡献值了。$
于是这道题就结束了，要注意的地方就是判重一定要用hash表，相减操作可能比mod小很多的时候要对被减得先模mod

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<bitset>
#include<stack>
#include<set>
#include<vector>
#include <time.h>
#include<string.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 2000000+10;
const int MOD = 2000007;
const int Mod = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double e=exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;
const int seed = 13131;#define Se second
#define Fi first
#define pb push_back
#define mk make_pairull P = 13331;
ull sqr[maxn],Hash_[maxn];
char str[maxn];
ull sumHash[maxn];
struct StringHash
{int first[MOD+2],num;unsigned long long EdgeNum[maxn];int next[maxn],close[maxn];void init (){num = 0;memset (first,0,sizeof first);return ;}int insert (unsigned long long val,int id){int u = val % MOD;for (int i = first[u]; i ; i = next[i]){if (val == EdgeNum[i]){int t = close[i];close[i] = id;return t;}}++num;EdgeNum[num] = val;close[num] = id;next[num] = first[u];first[u] = num;return 0;}
} H;
int r[maxn];
long long sum[maxn];
long long ans=0;
long long xp[maxn];
void init()
{xp[0]=1;for(int i=1;i<maxn;i++)xp[i]=(xp[i-1]*10)%Mod;return ;
}
void make_hash(char str[])//处理出str的hash值
{int len=strlen(str+1);sum[len+1]=0;for(int i=len;i>=1;i--){sum[i]=(sum[i+1]*10+str[i]-'0')%Mod;}return ;
}
ll Get_hash(int i,int L)
{return (sum[i]%Mod-sum[i+L]*xp[L]%Mod+Mod)%Mod;//注意这里要对被减的先取模
}
void insert_(int i,int j)
{ull now=Hash_[j]-Hash_[i-1]*sqr[j-i+1];if(!H.insert(now,1))//先判重，再插入{ans=(ans+Get_hash(i,j-i+1))%Mod;}
}
void solve(int n)
{sqr[0]=1;for(int i=1;i<=n;++i){sqr[i]=sqr[i-1]*P;Hash_[i]=Hash_[i-1]*P+str[i];}
}
ll manacher(int n)
{int x=0,pos=0;for(int i=1;i<=n;i++){int j=0;insert_(i,i);if(pos>i) j=min(r[2*x-i],pos-i);while(i+j+1<=n&&str[i+j+1]==str[i-j-1]){insert_(i-j-1,i+j+1);j++;}r[i]=j;if(i+j>pos){pos=i+j;x=i;}}x=0,pos=0;for(int i=2;i<=n;i++){int j=0;if(pos>i)j=min(r[2*x-i],pos-i+1);while(i+j<=n&&str[i+j]==str[i-j-1]){insert_(i-j-1,i+j);++j;}r[i]=j;if(i+j-1>pos){pos=i+j-1;x=i;}}
}
int main()
{scanf("%s",str+1);int n=strlen(str+1);init();//hash每一位的贡献预处理make_hash(str);//hash贡献值预处理solve(n);//hash表预处理manacher(n);//manacherprintf("%lld\n",ans);return 0;
}