Reduce string

Problem code: STREDUC

All submissions for this problem are available.

Give a string s of length l, and a set S of n sample string(s). We do reduce the string s using the set S by this way:

  • Wherever Si appears as a consecutive substring of the string s, you can delete (or not) it.
  • After each deletion, you will get a new string s by joining the part to the left and to the right of the deleted substring.

 

Request

By that way, try to reduce the given string s to get a new string of minimum length. You can do delete for unlimited times.

Input

 

  • The first line contains the string s.
  • The second line contains the integer n.
  • Within the last n lines, the i-th line contains the string Si.

 

Output

Output on a single line an integer which is the minimum length found.

Example

Input:

aaabccd
3
abc
ac
aaa

Output:

2

Limitations

 

  • 0<l?250
  • 0<n?30
  • 0<|Si|?20

 

NOTE: Because the testcases were created in Windows environment so it may be different from the Unix systems. The problems occur when using getline or gets because they tend to read '\r'. Instead using scanf("%s") or cin suffices for the given problem.

Author: anhdq
Date Added: 5-05-2010
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

Hi,I have the following

saik @ 31 Oct 2010 01:47 AM

Hi,

I have the following program, which gives a wrong output.

http://www.codechef.com/viewsolution/368716

As per my knowledge, all possible test cases were tested in my machine and they give the correct output.

Please advise.

 

Thanks,

saik

It must have taken you a long

triplem @ 31 Oct 2010 04:46 AM

It must have taken you a long time to test all possible cases on your machine, there are billions of them..

Anyway, your code gives the wrong answer for nearly every single test case. The simplest one which will fail:

ab
2
a
ab

Answer should of course be 0.

Hi, Thanks for the reply. The

saik @ 31 Oct 2010 03:39 PM

Hi,

Thanks for the reply.

The problem is, I misunderstood the first testcase.

Yes, the code fails whenever a single character is entered as the value for Si.

Will rework on the solution.

 

Thanks,

saik

It doesn't really matter

triplem @ 31 Oct 2010 03:45 PM

It doesn't really matter whether it is a single character or not. For example, you'd also give the wrong answer for abcd with substrings bc, ab, cd, since you would remove bc first.

I am confused here. As per

saik @ 31 Oct 2010 11:53 PM

I am confused here.

As per the problem,"Wherever Si appears as a consecutive substring of the string s, you can delete (or not) it."

So,in your example, should I not remove "bc" from "abcd" and form a new string "ad" ?

Please correct me if I am wrong.

 

Thanks

It says you can delete it. It

triplem @ 1 Nov 2010 02:44 AM

It says you can delete it. It doesn't say you have to.

If you delete bc, you get the string ad. However, if you instead delete ab first, then you can also delete cd and end up with a smaller string (in this case, of length 0). You want to remove strings in the right order so that you end up with the smallest possible string.

Hi. I use SemiDynamic method

iamhashemi @ 10 Jan 2012 05:17 PM
Hi. I use SemiDynamic method to solv problem. it is of order of n^2 * log(k) where n is size of input and k is number of members of s. in my pc every test time is less than one second.please send my a test case that results in 'time exceeded error'.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions