G2. 唐納德與子串 (Hard)

Time limit per test:?2.5 seconds

Memory limit:?512 megabytes

子串的定義是在一個字符串中連續(xù)出現(xiàn)的一段字符。這里，我們使用?s[l…r]?來表示?s?字符串從?l?到?r（閉區(qū)間）的子串。在本題中，字符串下標(biāo)從?0?開始。顯然，對于長度為?n?的字符串共有?n(n+1)2?個子串。

對于一個給定的字符串?s，唐納德給出?q?次詢問，第?i?次詢問包括三個參數(shù)?li,ri,zi，問在?s[li…ri]?的所有子串中共有多少個恰好為?zi。

Input

輸入具有如下形式：

sql1?r1?z1l2?r2?z2?lq?rq?zq

第一行一個字符串?s。

第二行一個整數(shù)?q。

接下來每行：首先兩個整數(shù)?li,ri?(0≤li≤ri<|s|)，然后是一個非空字符串?zi。整數(shù)和整數(shù)，整數(shù)和字符串間以單空格隔開。

字符串中只會出現(xiàn)?26?個小寫英文字母。

數(shù)據(jù)規(guī)模約定：

• 對于 Easy 檔：1≤|s|≤100,q≤∑|zi|≤100。
• 對于 Hard 檔：1≤|s|≤105,q≤∑|zi|≤105。

Output

對于每次詢問，輸出一個整數(shù)，表示答案。

Examples

input thisisagarbagecompetitionhahahah 5 0 30 a 1 5 is 25 30 hah 6 12 ag 7 12 ag output 6 2 2 2 1 #include <iostream> #include <cstring> using namespace std;int l,r,p,sum; int next[100000]; string s,z; void gtnext() {int k=-1,j=0;next[0]=-1;while(j<z.size()){if(k==-1||z[j]==z[k]){j++;k++;if(z[j]!=z[k])next[j]=k;elsenext[j]=next[k];}elsek=next[k];} } int kmp() {int j=l,k=0;while(j<=r){if(k==-1||s[j]==z[k]){j++;k++;}elsek=next[k];if(k==z.size()){sum++;k=next[k];}}cout<<sum<<endl; } int main() {cin>>s;cin>>p;for(int i=0;i<p;++i){sum=0;cin>>l>>r;cin>>z;memset(next,0,sizeof(next));gtnext();kmp();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的G2. 唐纳德与子串 (Hard)kmp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。