B. Segment Occurences

문자열 s,f가 주어졌을 때

숫자 a,b가 주어지고 s의 a번째 문자부터 b번째 문자열까지 안에 문자열 f가 몇번 나오는지 확인하는 문제.

매번 문자열 비교를 하면 O(q*n*m)라서 시간초과가 난다.

사전작업으로 매 위치에서 f와 같은지 비교 후 누적합으로 계산해놓으면 O(n*m+q)가 된다.

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
 
typedef long long ll;
 
char s[1002], t[1002];
int d[1002];
int n, m, q;
 
int main() {
    scanf("%d%d%d", &n, &m, &q);
    scanf(" %s %s", s + 1, t + 1);
    for (int i = 1; i <= n - m + 1; ++i) {
        d[i] = d[i - 1];
        int f = 1;
        for (int j = 1; j <= m; ++j) {
            if (t[j] != s[i + j - 1]) {
                f = 0;
                break;
            }
        }
        d[i] += f;
    }
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        b -= m - 1;
        printf("%d\n", b >= a - 1 ? d[b] - d[a - 1] : 0);
    }
    return 0;
}