本文主要是介绍POJ 3415 Common Substrings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Common Substrings
| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 13775 | Accepted: 4616 |
Description
A substring of a string T is defined as:
T(i, k)=TiTi+1...Ti+k-1, 1≤i≤i+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) | k≥K, 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 ≤ K ≤ min{|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这篇关于POJ 3415 Common Substrings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
