题意：给定两个串s和t，多次询问s的一个区间[l ,r]中有多少个子串与t串相同
len<=1e3,q<=1e5
思路：前缀和
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define MOD 1000000007 21 #define N 210000 22 23 char a[N+10],b[N+10]; 24 int s[N+10]; 25 ll n,m,q; 26 27 int read() 28 { 29 int v=0,f=1; 30 char c=getchar(); 31 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 32 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 33 return v*f; 34 } 35 36 37 int main() 38 { 39 //freopen("2.in","r",stdin); 40 //freopen("2.out","w",stdout); 41 scanf("%d%d%d",&n,&m,&q); 42 scanf("%s",a+1); 43 scanf("%s",b+1); 44 for(int i=0;i<=N-1;i++) s[i]=0; 45 for(int i=m;i<=n;i++) 46 { 47 int flag=1; 48 for(int j=1;j<=m;j++) 49 if(b[m-j+1]!=a[i-j+1]){flag=0;break;} 50 s[i]=s[i-1]+flag; 51 } 52 for(int i=1;i<=q;i++) 53 { 54 int x,y; 55 scanf("%d%d",&x,&y); 56 int t; 57 if(y-x+1<m) t=0; 58 else t=s[y]-s[x+m-2]; 59 printf("%d ",t); 60 } 61 return 0; 62 }