[itint 5]文字列マッチング

http://www.itint5.com/oj/#15
hashで作って、今までベストを尽くしたのもcase 16タイムアウト(20 w規模)で、ドラム缶でもタイムアウトしました.hashcodeを計算する時、'a'は1に計算します.そうでないと'a'が0なら、"a"と"a"は同じです.以下はタイムアウトのコードです.

#define BUCKET 65535

#define ulong long long



vector<unordered_set<ulong> > uset(BUCKET);

vector<ulong> pow26(11);



ulong hashcode(char *str, int n) {

    ulong code = 0;

    for (int i = 0; i < n; i++) {

        code = code * 26 + str[i] - 'a' + 1;

    }

    return code;

}



//       

void initWithString(char *str) {

    int len = 0;

    while (str[len] != '\0') {

        len++;

    }

    ulong num = 1;

    pow26[0] = 1;

    for (int i = 1; i <= 10; i++) {

        num *= 26;

        pow26[i] = num;

    }

    for (int l = 1; l <= 10; l++) {

        vector<ulong> codes(len);

        for (int i = 0; i < len; i++) {

            if (i + l <= len) {

                ulong code = 0l;

                if (i == 0) {

                    code = hashcode(str+i, l);

                    codes[i] = code;

                } else {

                    ulong diff = pow26[l-1];

                    diff *= (str[i-1] - 'a' + 1);

                    code = (codes[i-1] - diff) * 26 + str[i+l-1] - 'a' + 1;

                    codes[i] = code;

                }

				

                int buck = code % BUCKET;

                uset[buck].insert(code);

            }

        }

    }

}

//   query str   ,  true,    false

bool existSubString(char *query) {

    int len = strlen(query);

    ulong code = hashcode(query, len);

    int buck = code % BUCKET;

    if (uset[buck].find(code) != uset[buck].end()) {

        return true;

    } else {

        return false;

    }

}

長さが10の文字列だけを並べ替えられたvectorに預けて、二分でやってもいいです.注意ソース文字列の長さは10より小さいものがあります.他の代替方法には、trieおよび拡張配列がある.

vector<string> vec;



//       

void initWithString(char *str) {

    set<string> sset;

    int len = strlen(str);

    for (int i = 0; i < len; i++) {

		if (i + 10 >= len) {

			string sub(str+i);

			sset.insert(sub);

		} else {

			string sub(str+i, str+i+10);

			sset.insert(sub);

		}

    }

    

    for (set<string>::iterator it = sset.begin(); it != sset.end(); it++) {

        vec.push_back(*it);

    }

}

//   query str   ,  true,    false

bool existSubString(char *query) {

    string str(query);

    int low = 0;

    int high = vec.size()-1;

    

    while (low <= high) {

        int mid = (low + high) / 2;

        bool found = true;

        for (int i = 0; i < str.length(); i++) {

            if (vec[mid][i] < str[i]) {

                low = mid + 1;

                found = false;

                break;

            } else if (vec[mid][i] > str[i]) {

                high = mid - 1;

                found = false;

                break;

            }

        }

        if (found) return true;

    }

    return false;

}