codeforces1016B 字符串区间查找子串(数组前缀和防TLE)

题目链接：http://codeforces.com/problemset/problem/1016/B

题意是给你给两个字符串s，t，之后给出s的q个区间，对每个区间[l,r]询问s的这个区间中存在多少个子串与t相同

一开始的思路是每给出一个区间[L,R]。便在s相应的区间用KMP进行查找t出现的次数,但是大佬们说自己暴力过了这题。而我的暴力一直TLE。后来在排行榜上找了份大神的代码,原来他们的暴力是:预处理是用一个数组sum记录字符串中t出现的次数。sum[i]记录s串中前i个字符中t串(头部在i)出现的总次数。查找时直接利用端点的前缀和相减

思考：前缀和在很多题中的确可以节约重复的操作，例如查找区间[1，1000]，后又查找[2，1001]。则[2，1000]被重复查找，而利用前缀和便可以解决这个问题，一次查找记录了所有的信息。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <string>
#include <time.h>
#include <algorithm>
#include <set>
#include <stack>
#include <queue>
using namespace std;

char a[1005];
char b[1005];
int t[1005];
int sum[1005];

int main()
{
    memset(t,0,sizeof(t));
    int p, n, m;
    cin>>n>>m>>p;
    cin>>a>>b;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i+j]!=b[j])
                break;
            else if(j==m-1)
                //s串中t串出现的位置i(头)
                t[i]=1;
        }
    }

    sum[0]=t[0];
    for(int i=1;i<n;i++)
        //s串前i个字符中t串出现的次数是sum[i]
        sum[i]=sum[i-1]+t[i];

    while(p--)
    {
        int l, r;
        scanf("%d%d",&l, &r);
        l--, r--;
        if(n<m||r-l+1<m)
            cout<<0<<endl;
        else
        //查找区间[l, r]只需要两个区间端点的t串出现次数相减
            cout<<sum[r-m+1]-sum[l-1]<<endl;
    }

    return 0;
}