DCEPC810 - Cousin Wars

no tags 

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

hide comments
:D: 2012-10-03 19:28:26

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! :)

:D: 2012-10-02 23:24:37

How could the answer ever be negative? If A>B (string::compare again) the result is simply 0.

.:Ishant Shanu:.: 2012-09-11 12:08:53

@abbi031892 thnx

Last edit: 2012-09-11 12:09:32
_|_: 2012-08-25 11:24:05

Don't print negative answers...make it 0


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