Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Common Substrings
 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 17339 Accepted: 5757

Description

A substring of a string T is defined as:

T(i, k)=TiTi+1...Ti+k-1, 1≤ii+k-1≤|T|.

Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):

S = {(i, j, k) | kK, A(i, k)=B(j, k)}.

You are to give the value of |S| for specific A, B and K.

Input

The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.

1 ≤ |A|, |B| ≤ 105
1 ≤ Kmin{|A|, |B|}
Characters of A and B are all Latin letters.

Output

For each case, output an integer |S|.

Sample Input

```2
aababaa
abaabaa
1
xx
xx
0
```

Sample Output

```22
5
```

Source

[Submit]   [Go Back]   [Status]   [Discuss]