http://www.topcoder.com/stat?c=problem_statement&pm=6017&rd=8083

一道很好的题目，有几个tricky的地方需要注意：

1）对于[0,k][0,k]内的任一点(x,y)，该ray等同于(0,0)到(x%r,y%c)的ray。如果用brute-force枚举，即便用了KMP也会超时。

2）对于水平和竖直方向的ray，不要hard-code加到要考虑的list里面（考虑grid为{"a"}这样的情况），还是用gcd来判断。

3）用KMP而不是brute-force做string-match。

int gcd(int a, int b) {
    while (b != 0) {
        a %= b;
        a ^= b ^= a ^= b;
    }
    return a;
}

vector<vector<int> > suffixes;

vector<int> BuildSuffix(string pattern) {
    int lp = pattern.length();
    vector<int> pi(lp, -1);
    int k = -1;
    FOR(q,1,lp-1) {
        while (k >= 0 && pattern[k + 1] != pattern[q]) k = pi[k];
        if (pattern[k + 1] == pattern[q]) ++k;
        pi[q] = k;
    }
    return pi;
}

bool StringMatchKMP(string text, string pattern, vector<int> suffix) {
    int lt = text.length(), lp = pattern.length();
    int k = -1;
    REP(i,lt) {
        while (k >= 0 && pattern[k + 1] != text[i]) k = suffix[k];
        if (pattern[k + 1] == text[i]) ++k;
        if (k == lp - 1) return true;
    }
    return false;
}

int cnt[40][40];

class InfiniteSoup {
public:
    vector <int> countRays(vector <string> g, vector <string> words, int k) {
        int r = g.size(), c = g[0].length();

        suffixes.clear();
        REP(i,words.size()) suffixes.push_back(BuildSuffix(words[i]));

        memset(cnt, 0, sizeof(cnt));
        FOR(i,0,k) {
            FOR(j,0,k) {
                if (gcd(i, j) == 1) ++cnt[i % r][j % c];
            }
        }

        vector <int> res(words.size(), 0);

        REP(i,r) {
            REP(j,c) {
                if (cnt[i][j] > 0) {
                    string str = "";
                    int tr = 0, tc = 0;
                    do {
                        str += g[tr][tc];
                        tr = (tr + i) % r, tc = (tc + j) % c;
                    } while (tr || tc);

                    string t = str;
                    REP(k,50) t += str[k % str.length()];

                    REP(k,words.size()) {
                        if (StringMatchKMP(t, words[k], suffixes[k])) res[k] += cnt[i][j];
                    }
                }
            }
        }

        return res;
    }
};