http://codeforces.com/contest/914/problem/F

以前做过一个类似的，但是查询的子串长度最多是10，这个时候就是用bit +　ｈａｓｈ做了。这是因为改变一个字符，只需改变它后面１０个的ｈａｓｈ值就够了，多余的不影响，因为查询去不到那里。（只记得是今年的网络赛来的）

但是这题查询只给了一个长度总和，没上一题好做。

这题的思路应该是用bitset查询。

把各个字母拆成不同的bitset，比如abc，拆成

a: 001

b: 010

c: 100

然后，a & (b >> 1) & (c >> 2)即可。

最后统计bitset的L + lent - 1，R区间中有多少个1，这里需要用移位加速，不然TLE.

bitset的第0位，是最右边的。这也刚好， 相当于把整个串反转了    >> 后也可以把不需要的剔除

>> L位，是把左边的无关字符去掉

>> (R - L + 2 - lent)位是可以算出来的

具体就是，从L开始，假设有x位是合法的贡献，那么有L + x - 1 + lent - 1 = R

#include
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int MAXN = 1e5 + ;
bitset f[];
char str[MAXN];
char t[MAXN];
bitset getAns;
void work() {
scanf("%s", str + );
int lenstr = strlen(str + );
for (int i = ; i <= lenstr; ++i) f[str[i] - 'a'][i] = ; int q; scanf("%d", &q); while (q--) { int op; scanf("%d", &op); if (op == ) { int pos; scanf("%d%s", &pos, t); f[str[pos] - 'a'][pos] = ; str[pos] = t[]; f[str[pos] - 'a'][pos] = ; } else { int L, R; scanf("%d%d%s", &L, &R, t + ); int lent = strlen(t + ); if (lent > R - L + ) {
printf("0\n");
continue;
}
getAns.reset();
getAns = ~getAns;
for (int i = ; i <= lent; ++i) { getAns &= (f[t[i] - 'a'] >> (i - ));
}
// cout << getAns << endl; getAns >>= L;
// cout << getAns << endl; int ans = getAns.count(); getAns >>= (R - L + - lent);
// cout << getAns << endl;
ans -= getAns.count();
printf("%d\n", ans);
}
}
}

int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}