lc2781 最长合法子字符串的长度

给定长度为n且只包含小写字母的字符串word和禁用字符串数组forbidden，如果一个字符串不包含forbidden中的任何字符串，则称其为合法。求word中最长合法子字符串的长度，子字符串可以为空。
1<=n<=1e5; 1<=forbidden.length<=1e5; 1<=forbid[i].length<=10

注意到forbid[i]长度最大只有10，因此每次往右扩展到一个字符时，可以暴力算最多10个位置，判断是否为禁用词。由于判断时是逆序的，预处理禁用词时也采用逆序。另外遇到禁用词时，比如[l,r]是禁用词，那左端点应跳到l+1处继续开始。

using ll = long long;
class Solution {
public:
    ll id(const string &s) {
        ll h = 0;
        int n = s.size();
        for (int i = n-1; i >= 0; i--) {
            h = h * 26 + (s[i]-'a'+1);
        }
        return h;
    }
    int longestValidSubstring(string word, vector<string>& forbidden) {
        set<ll> dict;
        for (auto &s : forbidden) {
            dict.insert(id(s));
        }

        auto check = [&](int L, int R) -> int {
            ll h = 0;
            for (int i = R, j=1; i >= L && j <= 10; i--, j++) {
                h = h * 26 + (word[i]-'a'+1);
                if (dict.count(h)) {
                    return j;
                }
            }
            return 0;
        };

        int n = word.size();
        int ans = 0;
        for (int i = 0, j; i < n; i = j) {
            int d = 0;
            for (j = i; j < n; j++) {
                d = check(i,j);
                if (d > 0) {
                    break;
                }
            }
            ans = max(ans, j-i);
            if (i == j) {
                j = j+1;
            } else {
                j = j-d+2;
            }
        }
        return ans;
    }
};