F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Border Queries

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 71    Accepted Submission(s): 25


Problem Description
Given a string $S$ of length $n$ consisting of lowercase English letters. A partition of $S$ into three non-empty substrings $s_1,s_2,s_3$ is considered good if and only if $s_1$ is the border of $s_1+s_2$ and $s_3$ is the border of $s_2+s_3$. We say a string $s$ good if and only if $s$ is a substring of $S$ and there exists a good partition of $S$ into $s_1,s_2,s_3$ such that $s_2=s$.

Define the value of a string as the number of its good substrings. Two substrings are considered different if and only if the start position is different or the end position is different.

Given a string $T$ of length $m$ consisting of lowercase English letters and $q$ queries. In each query, you are given two integers $l,r$. You need to calculate the value of $T[l\cdots r]$.
 

Input
Each test contains multiple test cases. The first line contains an integer $T$ ($1\le T\le 60$) denoting the number of test cases.

For each test case, the first line contains three integers $n,m,q$ ($3\le n\le 10^6$, $1\le m,q\le 10^6$).

The second line contains a string $S$ of length $n$.

The third line contains a string $T$ of length $m$.

The next $q$ lines each contains two integers $l_i$ and $r_i$, denoting a query ($1\le l_i\le r_i\le m$).

It is guaranteed that $\sum n,\sum m,\sum q$ over all test cases does not exceed $10^6$.
 

Output
For each query, output one line with an integer denoting the answer.

Please do not output trailing spaces.
 

Sample Input
1 7 7 2 abacaba cabacab 1 4 3 7
 

Sample Output
0 2
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-26 05:11:23, Gzip enabled