Searching the String (ZOJ Problem Set - 3228)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3228

問題

文字列Aとクエリがn個与えられる。クエリには2つのタイプがあり、1つ目のタイプのクエリは文字列siが文字列Aの中に何回出ているかを数える物で、2つ目はoverlapを考えない場合の数を数える物である。各クエリを捌け。

A	<=10^5
si	<=6

n<=10^5

解法

Aを幅1〜6で区切ってtrieを作り、各文字が何回出現したか数える。2つ目のクエリ用のtrieは幅のサイズ-1までに同じ文字列が出現した場合は無視する。trieを作ってしまえば各クエリの文字が何回出てるか数えるだけで終わる。TLEやMLEが厳しいので頑張ること。