1673 - Smaller substrings

Time Limit : 2 Second

Memory Limit : 512 MB

Submission: 13

Solved: 1

Description

  Minieye team has independently developed a lot of leading computer vision algorithms. They specialize on research and development of the most professional, localized, and user-friendly ADAS products. They aim at popularizing the ADAS technology in a way that is more simple, intelligent and low-cost. Not surprisingly, sometimes minieye also need to deal with the strings.


  You are given two strings AB of alphabetic characters, you need to calculate


  1.how many substrings of A are smaller than B


  2.how many different substrings of A are smaller than B

Input

We have multiply cases. For each cases:


Each case contains two strings A and B,the length of A and B is no more than 500000.

Output

There should be one line per test case containing the two numbers for the two questions

sample input
3
abab  ac
abaab ac
aabab ac
sample output
6 4
10 7
11 8
hint

In first case, a,ab,aba,abab is smaller than ac, and there are 2 a, 2 ab,so the answer is 6 4

source
clq
© 2015 HUST ACMICPC TEAM. All Right Reserved.