POJ3294 Life Forms 哈希

这题的题意是给定N个串，某个串的子串在超过一半的串存在的话，那么这个串就是可取的，问满足这样的子串的最长长度是多少，如果有多个的话，按字典序输出。

这题我是用hash过的。大体步骤是这样的，首先保留最长串的长度，然后二分0-MAXNLEN得到答案，那么这里重点就是如何去写这个判定函数。二分里面只会传递一个参数那就是长度K，根据这个长度我们把所有的串都拆成长度为K的子串，这里有个优化就是使用一种hash规则能够在得到1 - N的hash的时候计算出2 - N+1的hash值，那么这里用到了经典的多项式插值取模的方法：假设有一个字符串a[0],a[1],a[2],a[4]，取长度为3的子串的时候，第一个子串的hash值是 a[0]*T^2 + a[1]*T + a[2] 第二个子串就是 a[1]*T^2 + a[2]*T+a[3], 这样一次for循环遍历就可以完成一个串的所有子串的hash了，具体就是先减去最前面的一项乘以后面的T的次方，整个KEY值乘以T，再加上后面的一项就可以了。这样的话，下次再判定是否为同一个串的时候只需要进入KEY%MOD的链表中寻找KEY值相同的串即可了，无须判定原始的字符串。

这里还有一个小优化就是二分答案的时候并不需要找完所有的子串，只要存在就可以退出了，最后一次查找就需要全部存储了。

代码如下：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <iostream> 
#define T 113
#define MOD 3001
using namespace std;

typedef unsigned long long UInt64;

struct Node
{
    UInt64 key;
    int NO, idx, cnt;
}info;

int N;

UInt64 mypow[1005];

char s[105][1005], temp[1005];

vector<string>vs;

vector<Node>val[MOD]; // 同一hash值的不同初始值 

vector<string>::iterator it;

bool Hash(int NO, int idx, UInt64 key, int k, int f)
{
    int Rkey = key % MOD, flag = 0;
    for (int i = 0; i < (int)val[Rkey].size(); ++i) {
        if (key == val[Rkey][i].key) {  // 说明这个串已经在这一轮中出现过
            flag = 1;
            if (NO != val[Rkey][i].NO) {  // 说明这是一个后加入的串 
                val[Rkey][i].NO = NO;
                val[Rkey][i].idx = idx;
                ++val[Rkey][i].cnt; 
                if (val[Rkey][i].cnt > (N>>1) && !f) {
                     return true;
                }
            }
        }
    }
    if (!flag) {
        info.cnt = 1, info.key = key;
        info.NO = NO, info.idx = idx;
        val[Rkey].push_back(info);
    }
    return false;
}

bool judge(int k, int f)
{
    int lim = N>>1;
    for (int i = 0; i < MOD; ++i) {  // 便利所有的Rkey 
        for (int j = 0; j < (int)val[i].size(); ++j) {
            if (val[i][j].cnt > lim) {
                if (!f) {
                    return true;
                }
                else {
                    memcpy(temp, s[val[i][j].NO]+val[i][j].idx, sizeof (char) * k);
                    temp[k] = '\0';
                    vs.push_back(temp);
                }
            }
        }
    }
    return false;
} 

void init()
{
    for (int i = 0; i < MOD; ++i) {
        val[i].clear();
    }    
}

inline bool Accept(int k, int f)
{
    int length;
    UInt64 key;
    init();
    for (int i = 1; i <= N; ++i) { 
        length = strlen(s[i]);
        if (length < k)    continue; // 长度小于k直接跳过 
        key = 0;
        for (int j = 0; j < k; ++j) {
            key = key * T + s[i][j];
        }
        if (Hash(i, 0, key, k, f) && !f) {
            return true;
        }
        for (int j = 1; j < length-k+1; ++j) { 
            key -= s[i][j-1] * mypow[k-1];
            key = key * T + s[i][j+k-1];
            if (Hash(i, j, key, k, f) && !f) {
                return true;
            }
        }
    }
//    puts("I am here~~");
    if (!f) {
        return false;
    }
    else {
        return judge(k, f);
    }
}

int bsearch(int l, int r)
{
    int mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Accept(mid, 0)) { // 这个长度可接受的话，那么就把长度变长
            l = mid + 1;
        }
        else {
            r = mid - 1;
        } 
    }
    return r; // r 一定是满足要求的最大解
}

int main()
{
    int MaxL, len, ans, first = 1;
    mypow[0] = 1;
    for (int i = 1; i <= 1000; ++i) {
        mypow[i] = mypow[i-1]*T; // unsigned 拥有这个自动对上界取模的特性 
    }
    while (scanf("%d", &N), N) {
        vs.clear();
        if (first) {  // 对空行的处理
            first = 0;
        }
        else {
            puts("");
        }
        MaxL = 0;
        for (int i = 1; i <= N; ++i) {
            scanf("%s", s[i]);
            len = strlen(s[i]);
            MaxL = max(MaxL, len); // 得到最长的串的长度进行二分
        }
        ans = bsearch(0, MaxL);
        if (ans <= 0) {
            puts("?");
        }
        else { 
            
            Accept(ans, 1);
            sort(vs.begin(), vs.end());
            for (it = vs.begin(); it != vs.end(); ++it) {
                cout << *it << endl;
            }
        }
    }
    return 0;
}