本题前置算法:0x0f 哈希 二分
首先对两个串做一遍字符串哈希 注意所用$base$相同(PS:本题使用unsigned long long自然溢出)
然后对于从前往后每一个位置作为l 二分一下匹配长度
牢记$hash_{sub[l,r]}$子串哈希值$Value = Hash[r] - Hash[l - 1] * base ^ {r - l + 1}$
当两个子串匹配成功时 那么两个子串的哈希值必然相同 因为前面共用了一个$base$
这时候记录一下
最后直接$O(Q)$处理一下询问
总复杂度$O(nlogn)$
有兴趣的可以试试KMP
过段时间会更新

Author:Miku_𝓜𝓪𝓼𝓽𝓮𝓻
Date:2021/5/26
下面是代码：

#include <bits/stdc++.h>

using namespace std ;

int read(int x = 0,bool f = false,char ch = getchar()) {
    for (;!isdigit(ch);ch = getchar()) f |= ch == '-' ;
    for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48) ; return f ? ~ x + 1 : x ;
}

const int N = 2e5 + 5 , base = 1331 ;

class Sulotion {
    private :
        int a , b , Q , x , sub_len , substr_len ;
        char sub[N] , substr[N] ;
        unsigned long long Hash[N] , Hsh[N] , p[N] ;
        int ans[N] ;
    public :
        Sulotion(){}
        #define sub_value(l,r) (Hash[r] - Hash[l - 1] * p[r - l + 1])
        #define substr_value(l,r) (Hsh[r] - Hsh[l - 1] * p[r - l + 1])
        void init() {
            a = read() , b = read() , Q = read() ;
            scanf("%s%s",sub + 1,substr + 1) ;
            return void() ;
        }
        void solve() {
            p[0] = 1 ; 
            sub_len = strlen(sub + 1) ;
            substr_len = strlen(substr + 1) ;
            for (int i = 1 ; i <= sub_len ; ++i )
                Hash[i] = Hash[i - 1] * base + sub[i] - 'a' + 1 ,
                p[i] = p[i - 1] * base ;
            for (int i = 1 ; i <= substr_len ; ++i )
                Hsh[i] = Hsh[i - 1] * base + substr[i] - 'a' + 1 ;
            return void() ;
        }
        void calc() {
            for (int i = 1 ; i <= sub_len ; ++i ) {
                int Vp , Tp , l , r , mid ;
                l = 0 , r = min(sub_len - i + 1,substr_len) ;
                while (l + 1 < r) {
                    mid = l + r >> 1 ;
                    Vp = sub_value(i,i + mid - 1) ;
                    Tp = substr_value(1,mid) ;
                    // cout << Vp << ' ' << Tp << ' ' << mid << endl ;
                    if (Vp == Tp) l = mid ;
                    else r = mid ;
                }
                // cout << i << ' ' << l << ' ' << r << ' ' ;
                Vp = sub_value(i,i + r - 1) ;
                Tp = substr_value(1,r) ;
                if (Vp == Tp) ++ ans[r] ;
                else ++ ans[l] ;
            }
        }
        void query() {
            while (Q--) {
               x = read() ;
               printf("%d\n",ans[x]) ; 
            } return void() ;
        }
} ;

signed main() {
    Sulotion* Answer = new Sulotion() ;
    Answer -> init() ;
    Answer -> solve() ;
    Answer -> calc() ;
    Answer -> query() ;
    return 0 ;
}