hash、hashtable

这题是真好，问我一共wa+tle共20+才做出来

正经做法好像是扩展kmp+字典树
但是，我想直接用hash做
于是我使用了hash
(我觉得hash是真的nb，太强了！适用范围太广了！必须要好好掌握的！)

首先输入就十分的困难
我们知道所有的字符串的长度之和的上限
但是因为字符串可能非常之多，所以我们难以求解分配给每一个字符串空间
在这里我学到了一个处理方法。
我们开一个上限空间的数组
然后每个字符串都搞一个头指针
这个指针指向上限数组中他们开始的位置。

真的非常的巧妙。very good

然后是下一个难关：
我们该如何hash呢？
我们想想哈，我们hash后肯定要统计个数。
那么这个统计个数，因为hash很大，我们不能依靠统计数组，只能依靠map

ok那么我们接下如何hash呢？
目前还美誉能卡掉双hash的问题
所以我上来就是双hash哦(推荐使用1e9+7和1e9+9 孪生素数很强的)
很快啊，然后tle

看样子双hash是会超时的。
然后我就使用了单hash了，我使用的是1e9+7不行！有冲突！！！！！！
太痛苦了。

然后我是用自然溢出ac了。。。。。。。
小知识：hash时理论上取模的数越大hash的冲突率就越小哦(当然不排除出题人故意卡你的情况)

如此似乎我们就完成了这道题了。
但是我再一看，我的时间5s+
这真的是太慢了！！！！！

怎么办呢？

我们分析了一下，不难发现在map这一步时我们加了一个log的复杂度
很伤，如果出题人再变态一点是会来卡人的。
那么如何解决这个问题？替代map！！！！！！！

我称呼其为hashtable
其实是不难的技巧
我们可以再算出hash值后，假设为v
然后将v对一个较小的素数取模，u=v%mod
然后将u记录在统计数组中。统计数组只要开到mod打就可以了。

然后我们将会面临hash冲突的风险。
如何规避这种风险呢？
我们可以在统计数组中每一索引处再开一个链表就可以了。
用类似链式向前星的形式，存储真实的hash值就好了。
建议，存储进去的值最好不要重复。我们可以再开一个数组记录这个点的值出现多少次了。
为什么这样做呢？因为这回减少链式向前星的长度，在一定程度上会起到制约复杂度飙升的作用。

如此改良后速度2s+
非常出色的hash运用。

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const int max_n = 2e6+100;
const int mod = 4000037;
const ll base = 23;
ll p[max_n],tot[max_n*3],*cur = tot;
char ss[max_n];
struct My_Hash{
    ll *ha;
    void init(int len){
        ha = cur;ha[0]=0;
        for (int i=1;i<=len;++i)ha[i]=ha[i-1]*base+ss[i-1];
        cur+=len+2;
    }
    ll gethash(int l, int r){
        return ha[r]-ha[l-1]*p[r-l+1];
    }
}S[max_n],S2[max_n];


struct hashtable{
    int head[mod+5],net[max_n],cnt;
    ll to[max_n],cct[max_n];
    void init(){
        fill(to,to+max_n,-1);cnt=1;
    }
    void insert(ll v){
        int u = v%mod;
        for (int i=head[u];i;i=net[i]){
            if (to[i]==v){
                ++cct[i];
                return;
            }
        }
        to[cnt]=v;cct[cnt]=1;
        net[cnt]=head[u];head[u]=cnt++;
    }
    ll quiry(ll v){
        int u = v%mod;
        for (int i=head[u];i;i=net[i])
            if (to[i]==v)return cct[i];
        return 0;
    }
}HT;
int len[max_n];
int main(){
    int n;scanf("%d",&n);p[0]=1;
    HT.init();
    for (int i=1;i<max_n;++i)p[i]=p[i-1]*base;
    for (int i=1;i<=n;++i){
        scanf("%d %s",&len[i],ss);
        S[i].init(len[i]);
        HT.insert(S[i].gethash(1,len[i]));
        for (int j=0;j<=len[i]/2-1;++j)swap(ss[j],ss[len[i]-j-1]);
        S2[i].init(len[i]);
    }ll ans = 0;
    for (int i=1;i<=n;++i){
        int m = len[i];
        for (int r = 1;r<m;++r)
            if (S[i].gethash(1,r)==S2[i].gethash(m-r+1,m))
                ans+=HT.quiry(S2[i].gethash(1,m-r));
        for (int l=m;l>1;--l)
            if (S[i].gethash(l,m)==S2[i].gethash(1,m-l+1))
                ans+=HT.quiry(S2[i].gethash(m-l+2,m));
        ans+=HT.quiry(S2[i].gethash(1,m));
    }printf("%lld\n",ans);
}