DCEPC810 - Cousin Wars

Sunny is fond of words. He got a new game to play with his cousin Sonali. He gives her a long string and two other smaller strings (A and B). Now he asks Sonali to find the number of all the subsequences of the long string that are greater than equal to smaller string A and less than equal to smaller string B.

Help Sonali to find the answer.

Note : Comparison of two strings is regarded same as that done by theĀ string:compare function.

Empty string is not regarded as a subsequence.

Input

Each input consists of 3 lines. First line has the TEXT string.

2nd and 3rd line contain two smaller strings A and B.

Output

One number which gives the count such that A <= subsequence of (TEXT) <= B.

Constraints

Input will consist of all lowercase characters.

1 <= Length of TEXT <= 25

1<= Length of A and B <= Length of TEXT

Example

Input:
coforc
co
fc

Output:
24

Added by:dce coders
Date:2012-08-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2022-03-02 19:05:18
also check if A > B. in that case print 0.

Last edit: 2022-03-02 19:08:35
2012-10-03 19:28:26 :D
I felt if was a pretty easy problem. Not trivial by any means, but there should really be more AC submissions. Get to work people! :)
2012-10-02 23:24:37 :D
How could the answer ever be negative? If A>B (string::compare again) the result is simply 0.
2012-09-11 12:08:53 .:Ishant Shanu:.
@abbi031892 thnx

Last edit: 2012-09-11 12:09:32
2012-08-25 11:24:05 _|_
Don't print negative answers...make it 0
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.